Kosmiczna łamigłówka

Grupa młodsza

Limit pamięci: 32MB

Pewnego dnia król Bajtazar obudził się z ogromnym bólem głowy w dziwnym sześciennym pomieszczeniu. Obok niego leżał list: 

Drogi Bajtazarze,

Zostałeś  wybrany spośród wszystkich mieszkańców Bajtocji jako ten, który dostąpi zaszczytu zmierzenia się z naszym testem. 
Umieściliśmy Cię w najnowszej konstrukcji organizacji Kosmici i spółka – sześciennej kostce o wymiarach N x N x N, składającej się z N^3 jednostkowych pokoi takich jak ten, w którym się teraz znajdujesz. Z każdego z nich możesz przejść do 6 innych, sąsiadujących z nim (również tych nad i pod). Ponadto każdemu pokojowi przyporządkowaliśmy pewną liczbę naturalną.

Pozwolimy Ci powrócić  do Twojego królestwa, gdy uda Ci się  opuścić naszą konstrukcję-łamigłówkę  (tzn. dojść do pokoju leżącego na jednej ze ścian sześcianu, a następnie przejść tam, gdzie nie ma już pokoju). Oprócz tego czeka tu już na Ciebie drobny poczęstunek w postaci ciasta, które otrzymasz zaraz po ukończeniu testu.

Uważaj jednak – w pokojach, którym przyporządkowane są liczby złożone lub jedynka (tzn. nie pierwsze) umieściliśmy teleportery, które przeniosą Cię do galaktyki NGC 7766, a wówczas prawdopodobnie już nigdy nie ujrzysz swoich poddanych.

Mimo to wierzymy, że uda Ci się je ominąć i tym samym pomyślnie ukończyć  nasz test. 

Z poważaniem, 
Zespół nr 39 działający w ramach wydziału do spraw badań nad obcymi w międzygalaktycznej organizacji Kosmici i spółka 
 
 
PS. Do listu dołączamy mapę wraz z liczbami przyporządkowanymi poszczególnym pokojom, aby ułatwić Ci nieco zadanie.


I rzeczywiście, do listu dołączone było małe urządzenie elektroniczne z guzikiem, po naciśnięciu którego oczom Bajtazara ukazała się holograficzna, trójwymiarowa mapa kosmicznej łamigłówki. Ponadto na mapie widniały liczby przyporządkowane poszczególnym pokojom.

Twoim zadaniem jest pomóc Bajtazarowi powrócić do Bajtocji poprzez określenie ile najmniej pokoi będzie musiał on odwiedzić, aby wydostać się ze strasznego labiryntu.
 

Wejście:

W pierwszej linii wejścia znajduje się liczba N (1<=N<=100).

Druga linia jest pusta.

Dalej następuje opis N pięter konstrukcji. Każdy z takich opisów składa się z N linii, po N liczb naturalnych w każdej. Są to liczby przyporządkowane poszczególnym pokojom przez kosmitów. Możesz założyć, iż będą one nie większe niż 10^6. Wyjątkiem jest liczba 0, oznaczająca pokój, w którym znajduje się Bajtazar. Jako że nie opanował on jeszcze trudnej sztuki bilokacji, możesz założyć, iż na wejściu pojawi się ona tylko raz.

Ponadto każde dwa opisy pięter oddzielone są pustą linią. 

Wyjście

W pierwszej linii standardowego wyjścia wypisz jedną liczbę naturalną, określającą ile pokoi będzie musiał odwiedzić Bajtazar, aby wydostać się z konstrukcji kosmitów lub 0, jeśli został on przez nich oszukany i nie ma szansy już kiedykolwiek zobaczyć swych poddanych (a także zasmakować kosmicznego ciasta).

Przykład:

Wejście: Wyjście:
3 

3 5 7

6 4 9

2 3 4 

4 8 6

4 0 3

1 4 6 

4 6 9

3 7 2

5 3 5

 2
 

Wyjaśnienie do przykładu: 
Bajtazar znajduje się w środkowym pokoju kostki o wymiarach 3 x 3 x 3. Wydostać może się zatem na wiele sposobów, z których następujące 2 zapewnią mu odwiedzenie najmniejszej możliwej liczby pokoi:

  1. Bajtazar idzie do pokoju „na prawo” (o numerze 3) znajdującego się na tym samym piętrze, a następnie opuszcza kostkę.
  2. Bajtazar idzie do pokoju o numerze 7 znajdującego się piętro wyżej, po czym opuszcza kostkę.

W obu tych przypadkach Bajtazar odwiedzi 2 pokoje: ten w którym znajdował się na początku oraz ten do którego przeszedł tuż przed opuszczeniem kostki. Odpowiedzią jest zatem liczba 2.