Fişierul intrare/ieşire:robots.in, robots.outSursăBaraj Shumen 2012, Seniori
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie60000 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Robots

Se dă o tablă pătrată cu N linii şi N coloane, numerotate de la 1 la N. Unele pătrate sunt blocate de obstacole. La coordonatele (L1, C1) şi (L2, C2) sunt amplasaţi doi roboţi. O mutare constă din deplasarea unui singur robot. Fiecare robot se poate deplasa pe tablă în linie dreaptă (vertical sau orizontal), dar nu se poate opri decât când se ciocneşte de un perete, de marginea tablei sau de celălalt robot. În imaginea alăturată, robotul de la coordonatele (4, 5) are trei mutări posibile: la (4, 2) (unde se ciocneşte de celălalt robot), la (2, 5) (unde se ciocneşte de obstacol) sau la (4, 6) (unde se ciocneşte de marginea din dreapta). El nu se poate deplasa în jos, căci este deja la marginea de jos a tablei.

Să se găsească o succesiune cât mai scurtă de mutări prin care robotul 1 ajunge la coordonatele finale (L3, C3).

Date de intrare

Fişierul de intrare robots.in conţine pe prima linie dimensiunea tablei, N. A doua linie conţine coordonatele L1, C1, L2, C2, L3, C3. Următoarele N linii conţin fiecare câte N numere de 0 (pătrat circulabil) sau 1 (obstacol), separate prin spaţii.

Date de ieşire

În fişierul de ieşire robots.out se va scrie pe prima linie numărul minim K de mutări necesare. Pe fiecare din următoarele K linii se vor scrie tripleţi de numere K L C cu semnificaţia "Mută robotul K la coordonatele (L, C) (evident, K este 1 sau 2).

Dacă nu există o succesiune de mutări care să deplaseze robotul 1 la coordonatele (L3, C3), în fişierul de ieşire se va scrie doar numărul -1.

Dacă există mai multe soluţii de lungime minimă, o puteţi tipări pe oricare.

Restricţii

  • 3 <= N <= 50
  • 1 <= L1, C1, L2, C2, L3, C3 <= N
  • Pătratele (L1, C1), (L2, C2) şi (L3, C3) sunt distincte şi nu conţin obstacole.

Exemplu

robots.inrobots.outExplicaţie
4
4 1 1 2 1 3
0 0 0 0
1 0 0 1
0 0 0 0
0 0 0 0
4
1 4 4
2 4 2
1 4 3
1 1 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici