Alge

alge

== include(page="template/taskheader" task_id="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ă.

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 ng {@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ă.

h2. 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).

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ă.

h2. Date de intrare

Î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$})).

* 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)$).

h2. Restricţii

* {$2$} ≤ $N$ ≤ {$35$}
* {$0$} ≤ $M$ ≤ {$30$}

* {$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.

h3. 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$}).

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)$.

== include(page="template/taskfooter" task_id="alge") ==

== include(page="template/taskfooter" 3725="alge") ==

3725