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

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

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(cu 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ă.Pestisorul se poate deplasa dintr-un cub in alt cub adiacent(cele doua cuburi au un patrat comun).

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") ==