== include(page="template/taskheader" task_id="perspico") ==
Poveste şi cerinţă...
Inspirată de faimosul Perspico, Miruna se gândeşte la următorul joc: se dă o matrice cu $N$ linii şi $M$ coloane în care fiecare număr între $0$ şi $N * M - 1$ apare exact o singură dată. O mutare validă în acest joc constă din interschimbarea elementului $0$ cu unul dintre cei $4$ vecini ai săi. Miruna câştigă dacă reuşeşte să aducă matricea în următoarea configuraţie:
* pe orice poziţie $(x, y)$, cu excepţia poziţiei $(N, M)$, trebuie să se găsească valoarea $(x - 1) * M + y$;
* pe poziţia $(N, M)$ trebuie să se găsească valoarea $0$.
h2. Cerinţă
Fiind dată o configuraţie a jocului, ajutaţi-o pe Miruna să îl termine, iar ea vă va răsplăti cu un pupic ;).
h2. Date de intrare
Fişierul de intrare $perspico.in$ ...
Pe prima linie din fişierul de intrare $perspico.in$ se află două numere întregi $N$ şi $M$, având semnificaţia din enunţ. Următoarele $N$ linii vor conţine câte $M$ numere naturale, reprezentând elementele matricei.
h2. Date de ieşire
În fişierul de ieşire $perspico.out$ ...
În fişierul de ieşire $perspico.out$ se vor scrie mai multe numere naturale din intervalul $[1, 4]$, reprezentând mutările efectuate, codificarea lor fiind următoarea:
* 1 – Dacă elementul $0$ se interschimbă cu cel de deasupra.
* 2 – Dacă elementul $0$ se interschimbă cu cel din dreapta.
* 3 – Dacă elementul $0$ se interschimbă cu cel de dedesubt.
* 4 – Dacă elementul $0$ se interschimbă cu cel din stânga.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N, M ≤ 64$
* Dacă există mai multe soluţii poate fi afişată oricare.
* Se garantează că pe toate fişierele de test există cel puţin o soluţie.
h2. Exemplu
table(example). |_. perspico.in |_. perspico.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3
0 1 3
4 2 6
7 5 8
| 2 3 3 2
|
h3. Explicaţie
...
Mutările efectuate vor fi în direcţiile: $E$, $S$, $S$, $E$. După efectuarea lor matricea va arăta astfel:
$1 2 3$
$4 5 6$
$7 8 0$
== include(page="template/taskfooter" task_id="perspico") ==
