Fişierul intrare/ieşire:	alge.in, alge.out	Sursă	OLI 2009, Bucuresti, clasele 11-12
Autor	Dan Grigoriu	Adăugată de	Andrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test	0.05 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Alge

Un acvariu de forma cubică şi latură n se secţionează, mai întâi, cu N-1 plane orizontale şi echidistante, obţinându-se N niveluri de grosime 1, numerotate de la 1 la N (1 pentru cel de sus), apoi se secţionează cu N-1 plane verticale echidistante şi paralele cu feţele laterale stânga-dreapta obţinându-se N lame de grosime 1, numerotate de la 1 la N ( 1 pentru cea din stânga), iar la final se secţionează cu N-1 plane verticale, echidistante şi paralele cu feţele laterale faţă-spate, obţinându-se N lame de grosime 1, numerotate de la 1 la N ( 1 pentru cea din faţă). Coordonatele unui cub cu latura 1 din secţiune sunt în ordine: prima coordonată pentru nivel, a doua pentru lama stânga-dreapta şi a treia pentru lama faţă-spate. În acvariu se găsesc M grupuri de alge. Grupurile au forma cubică, fiind situate în cuburi cu latura 1 din secţiune, şi sunt dispuse astfel încât să nu se atingă între ele, nici măcar printr-un vârf de algă.

Cerinta

Să se determine un drum în acvariu pentru un peştişor, care trebuie să plece din cubul de secţiune situat în colţul stânga-faţă-sus, de coordonate (1,1,1), şi să ajungă în cubul de secţiune situat colţul dreapta-spate-jos, de coordonate (N,N,N), fără să treacă prin niciun grup de alge, iar drumul să fie de lungime minimă.Pestisorul se poate deplasa dintr-un cub in alt cub adiacent(cele doua cuburi au un patrat comun).

Date de intrare

Fişierul alge.in conţine pe prima linie cele două numere naturale N şi M, separate de printr-un spaţiu. Pe fiecare din următoarele M linii, sunt scrise câte 3 numere naturale, separate prin câte un spaţiu, reprezentând cele 3 coordonate cubului cu latura 1 din secţiune în care este situat un grup de alge. 

Date de ieşire

În fişierul alge.out se vor scrie:

• pe prima linie un număr natural k reprezentând lungimea drumului minim
• pe fiecare dintre următoarele k linii sunt scrise câte trei numere naturale, separate prin câte un spaţiu, reprezentând coordonatele cuburilor cu latura 1 din secţiune prin care trece drumul de lungime minimă. Fiecare triplet reprezintă coordonatele unei poziţii în drumul peştişorului (prima poziţie va fi (1,1,1) iar ultima (N,N,N)).

Restricţii

• 2 ≤ N ≤ 35
• 0 ≤ M ≤ 30
• Cuburile, cu latura 1 din secţiune, situate în colţurile stânga-faţă-sus şi dreapta-spate-jos nu sunt ocupate de alge. 
• Lungimea drumului este egală cu numărul de cuburi cu latura 1 din secţiune prin care trece peştişorul
• Pot exista mai multe drumuri de lungime minimă. Se cere o singură soluţie.

Exemplu

Explicaţie

Acvariul are latura de 3 şi există un singur grup de alge situat în cubul cu latura 2 din secţiune de coordonate (3,1,1), adica este lipit de colţul faţă-stânga-jos al acvariului.
Drumul de lungime minimă al peştisorului trece prin k=7 cuburi cu latura 1 din secţiune, şi anume: din cubul de coordonate (1,1,1), în linie dreapta spre spatele acvariului, până în cubul de coordonate (1,1,3), apoi la dreapta spre cubul de coordonate (1,3,3) şi apoi în jos, până în cubul de coordonate (3,3,3).

Cum se trimit solutii?