Fişierul intrare/ieşire:perspico.in, perspico.outSursăLot Bistrita 2009, Baraj 2
AutorAndrei GrigoreanAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.225 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inperspico.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content