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(cu 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?