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ę-
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.
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ą.
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:
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.
[Zgłoś rozwiązanie] [Moje zgłoszenia]