| Fişierul intrare/ieşire: | perspico.in, perspico.out | Sursă | Lot Bistrita 2009, Baraj 2 |
| Autor | Andrei Grigorean | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Perspico
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.
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 ;).
Date de intrare
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.
Date de ieşire
Î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.
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.
Exemplu
| perspico.in | perspico.out |
|---|---|
| 3 3 0 1 3 4 2 6 7 5 8 | 2 3 3 2 |
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
