W tym zadaniu interaktywnym musisz dotrzeć od wejścia nieznanego labiryntu do jego wyjścia, nie tracąc zbyt wiele czasu.
Słynny wojownik Malcolm, bohater Arcania, szedł nocą przez ciemny las. Wędrował długo i zaczął podejrzewać, że się zgubił, lecz nagle natknął się na kamienny mur na swojej drodze. Znaki na kamiennej płycie, widoczne spod opadłych liści, jasno wskazywały, że odkrył labirynt zbudowany przez krasnoludy.
Bohater niewiele wie o lesie i rosnących w nim drzewach. Na szczęście spędził wiele czasu w towarzystwie krasnoludów, więc teraz potrafi wiele powiedzieć o labiryncie, patrząc tylko na jego oznaczenia.
Oznaczenia na tym labiryncie tworzą znaki „SK3”. Znak „S” oznacza, że labirynt jest kwadratem, czyli jego podłoga składa się z $n \times n$ kwadratowych pól o wymiarach $1 \times 1$ metr każde. Pola otacza cienki, ciągły mur z dwoma otworami. Pierwszy jest wejściem, przy którym stoi bohater. Znajduje się w południowej ścianie południowo-zachodniego narożnego pola labiryntu. Drugi otwór jest wyjściem w północnej ścianie północno-wschodniego narożnego pola labiryntu.
Każde dwa pola mające wspólny bok mogą być połączone przejściem lub rozdzielone odcinkiem cienkiej ściany wewnętrznej o długości jednego metra. Z każdego pola labiryntu można przejść na dowolne pole mające z nim wspólny bok, o ile nie ma między nimi ściany. Ponadto przez wyjście można przechodzić swobodnie. Wejście pozostaje otwarte tylko do chwili, gdy bohater wejdzie do labiryntu. Następnie natychmiast się zamyka i otwiera ponownie dopiero wtedy, gdy bohater bezpiecznie dotrze do wyjścia.
Znaki „K3” informują doświadczonego wędrowca, że labirynt ma następującą strukturę. Najpierw spośród wszystkich możliwych odcinków cienkich ścian wewnętrznych (jest łącznie $n \times (n-1)$ odcinków północ–południe i tyle samo odcinków wschód–zachód) wybiera się losowo jedną trzecią, zaokrąglając w dół, i rozpatruje w ustalonej losowej kolejności. Następnie odcinki umieszcza się w labiryncie w tej kolejności. Jeśli umieszczenie jakiegoś odcinka podzieliłoby kwadrat zawierający labirynt na niepołączone części, odcinek ten jest odrzucany i nie zostaje umieszczony. Gwarantuje to spójność powstałego labiryntu.
Malcolm się ucieszył: wie o labiryncie tak wiele, że z pewnością dotrze do wyjścia. Jego celem jest wyruszyć z pola lasu przylegającego do wejścia i dotrzeć na pole lasu przylegające do wyjścia. Powinien się też spieszyć: osoba, która dostatecznie szybko pokona drogę od wejścia do wyjścia, zobaczy skarb ukryty w lesie w pobliżu wyjścia. Oczywiście jest tak tylko wtedy, gdy nikt wcześniej nie dotarł do skarbu.
Po namyśle pojawiają się jednak powody do niepokoju. Po pierwsze, Malcolm nie zna rozmiaru labiryntu: długość boku kwadratu $n$ może być dowolną całkowitą liczbą metrów od $10$ do $200$. Po drugie, labirynt jest równie ciemny jak otaczający las, więc Malcolm musi poruszać się niemal po omacku. Na początku każdego kroku bohater wybiera jeden z czterech głównych kierunków: północ, wschód, południe lub zachód. Następnie próbuje przesunąć się o jeden metr w tym kierunku. Jeśli napotka przeszkodę, pozostaje na miejscu. W przeciwnym razie przechodzi na sąsiednie pole w wybranym kierunku. Czas każdego kroku nie zależy od jego wyniku, zatem liczy się łączna liczba kroków.
Pomóż bohaterowi poruszać się tak, aby dostatecznie szybko dotarł na wymagane pole. Rozwiązanie zostanie uznane za poprawne, jeśli bohater wykona najwyżej $5 \cdot n + 300$ kroków i dotrze na pole znajdujące się poza wyjściem z labiryntu.
Interakcja
W tym zadaniu program jury reaguje na polecenia wypisywane przez rozwiązanie na standardowe wyjście. Każde polecenie określa kolejny krok Malcolma. Polecenie zapisuje się w osobnym wierszu i składa się ono z jednej wielkiej litery alfabetu angielskiego: „N” oznacza krok na północ, „E” na wschód, „S” na południe, a „W” na zachód.
Na każde wydane polecenie program jury natychmiast odpowiada wierszem przekazanym na standardowe wejście rozwiązania. Wiersz zawiera jedno słowo zapisane małymi literami angielskimi: „no”, jeśli przeszkoda uniemożliwiła przejście; „ok”, jeśli krok się udał, lecz bohater nie dotarł na pole docelowe; oraz „end”, jeśli krok się udał i bohater znalazł się na polu docelowym. Po otrzymaniu odpowiedzi „end” rozwiązanie musi zakończyć działanie bez wypisywania czegokolwiek więcej.
Aby uniknąć buforowania wyjścia, po każdym poleceniu opróżnij bufor wyjścia. Można to zrobić na przykład za pomocą fflush (stdout) w C lub C++, System.out.flush () w Javie, flush (output) w Pascalu albo sys.stdout.flush () w Pythonie.
W każdym teście labirynt jest z góry ustalony po losowym wygenerowaniu.
Jeśli rozwiązanie wykonało co najmniej $100\,000$ kroków, lecz nie przekroczyło jeszcze limitu czasu i nie dotarło na pole docelowe, testowanie zostaje zakończone wynikiem „Błędna odpowiedź”.
Przykład
Uwagi
Powyższy rysunek przedstawia labirynt wygenerowany w pierwszym teście. Malcolm zaczyna na polu oznaczonym kółkiem i musi dotrzeć na pole oznaczone krzyżykiem. Labirynt można przejść na przykład za pomocą następującej sekwencji poleceń (poniżej poleceń podano wyniki ich wykonania):
N W N E N W N E N E E E S E E N N N N N E N E S E E N ok no ok ok ok ok ok ok ok ok ok no ok ok ok ok ok ok ok ok ok ok ok no ok ok end
Na rysunku rozwiązanie to zaznaczono grubą szarą linią.