Podziemne miasto

Jesteś uwięziony w jednym z podziemnych miast Kapadocji. Błądząc w ciemnościach znalazłeś przypadkiem plan miasta. Niestety na planie nie jest zaznaczone miejsce, w którym jesteś. Badanie miasta pomoże Ci je znaleźć i na tym polega Twoje zadanie.

Plan jest prostokątna siatką jednostkowych kwadratów. Każdy kwadrat jest albo otwartym kawałkiem przestrzeni, krócej, jest otwarty i wtedy jest oznaczony literą 'O', albo jest częścią muru i wtedy jest oznaczony literą 'W'. Na planie jest zaznaczony kierunek północny. Na szczęście masz przy sobie kompas i możesz poprawnie zorientować swój plan. Na początku jesteś w kwadracie otwartym.

Wszystko zaczyna się od wywołania bezargumentowej procedury (albo funkcji) start. Możesz badać miasto z pomocą procedur (lub funkcji) look oraz move.

Możesz zadawać pytania w postaci wywołania funkcji look(dir), gdzie dir oznacza kierunek, w którym spoglądasz, przedstawiony jako jedna z liter 'N', 'S', 'E' oraz 'W', oznaczających odpowiednio północ, południe, wschód i zachód. Załóżmy teraz, iż wartością argumentu wywołania dir jest 'N'. Odpowiedzią będzie litera 'O', jeśli kwadrat na północ od Ciebie jest otwarty, zaś 'W' jeśli jest częścią muru. Podobnie można spoglądać w innych kierunkach i zbierać informacje o innych sąsiednich kwadratach.

Możesz wejść na jeden z czterech sąsiednich kwadratów, wywołując move(dir), gdzie dir oznacza kierunek kroku wykonywanego w opisany wyżej sposób. Możesz przechodzić tylko na kwadraty otwarte. Próba wejścia na kwadrat będący częścią muru byłaby ciężkim błędem. Do każdego otwartego kwadratu w mieście można dojść z dowolnego innego otwartego kwadratu.

Masz znaleźć, z pomocą najmniejszej możliwej liczby spojrzeń (wywołań procedury look(dir)), położenie otwartego kwadratu, w którym znalazłeś plan. Zaraz po znalezieniu tego położenia musisz go przekazać z pomocą wywołania procedury finish(x,y), gdzie x jest współrzędną poziomą (zachód-wschód), zaś y jest współrzędna pionowa (południe-północ) położenia.

Założenia

• , gdzie U jest szerokością planu, to znaczy długością mierzoną liczbą kwadratów w kierunku poziomym (zachód-wschód).
• , gdzie V jest wysokością planu, to znaczy długością mierzoną liczbą kwadratów w kierunku (południe-północ).
• Miasto jest otoczone murami, które są przedstawione na planie.
• Południowo-zachodni róg miasta ma współrzędne (1,1), zaś północno-wschodni ma współrzędne (U,V).

Wejście

Plikiem wejściowym jest plik tekstowy under.inp.

• Pierwszy wiersz zawiera dwie liczby: U, V.
• Każdy z następnych V wierszy zawiera wiersz planu w kierunku poziomym. Każdy wiersz składa się z U znaków, a x-ty znak w (V-y+2)-im wierszu pliku wejściowego podaje informacje o kwadracie planu, mającym współrzędne (x,y): jest to albo litera 'W' oznaczająca mur, albo litera 'O' oznaczająca otwarty kwadrat. Dane w tych wierszach nie są pooddzielane żadnymi odstępami.

Wyjście

Nie generuje się żadnego pliku wyjściowego. Wynik znaleziony przez Twój program należy przekazać wywołując procedurę finish(x,y).

Przykład

under.inp:

5 8
WWWWW
WWWOW
WWWOW
WOOOW
WOWOW
WOOWW
WWOOW
WWWWW

Możliwa interakcja, kończąca się poprawnym wywołaniem procedury finish:

Interaction:
Start()

look('N')
'W'
look('E')
'O'
move('E')

look('E')
'W'
finish(3,5)

Wytyczne dla programujących w Pascalu

Powinieneś mieć w swoim pliku źródłowym zapisane:

Ten moduł zapewni Ci dostęp do:

procedure start;  naleťy wywoŞa˘ w pierwszej kolejnoąci
function look (dir:char):char; 
procedure move (dir:char); 
procedure finish (x,y:integer);  wywoŞa˘ jako ostatniĄ 

Wytyczne dla programujących w C/C++

Powinieneś mieć w swoim pliku źródłowym:

Zapewni Ci to następujące deklaracje:

void start (void); /* naleťy wykona˘ w pierwszej kolejnoąci*/
char look (char);
void move (char);
void finish (int,int); /* wykona˘ jako ostatniĄ */

Utwórz również projekt, nazwany under, który powinien zawierać Twój program oraz bibliotekę służącą do interakcji, nazwana underobj.obj. Żeby utworzyć projekt, należy wybrać z menu project opcje open, a następnie za pomocą opcji add item dołączyć twój plik źródłowy (under.c lub under.cpp) oraz plik underobj.obj. W trakcie kompilacji korzystaj z modelu pamięci LARGE. (UWAGA: Jest to zmiana ustalenia podanego w Regulaminie Zawodów.)

Ocena

Ograniczenie na czas działania programu wynosi 5 sekund.

Aby otrzymać maksymalną liczbę punktów A za test, liczba wywołań x funkcji look nie może przekraczać ograniczenia M ustalonego przez program oceniający. Liczba M jest większa (>) od minimum. W szczególności, M nie zależy od tego, czy kolejność kierunków spoglądania jest zgodna, czy przeciwna do kierunku ruchu wskazówek zegara. Jeśli twój program wywoła funkcje look więcej niż (>) M razy, ale mniej niż (<) dwa razy M, to możesz otrzymać część punktów. W takim przypadku liczba punktów jest wyliczana zgodnie z następującą formułą (zaokrąglając do najbliższej liczby całkowitej):

Jeśli twój program zachowa się w sposób niedozwolony, to otrzymasz 0 punktów. Niedozwolone zachowania programu w tym zadaniu to:

• wywołanie procedury lub funkcji bibliotecznej z niedozwolonym parametrem, np. ze znakiem nie oznaczającym kierunku,
• próba wejścia w ścianę,
• nie przestrzeganie wytycznych.

Jak testować program

Utwórz plik tekstowy place.txt zawierający miejsce znalezienia planu. Uruchom program. Obejrzyj wyniki znajdujące się w pliku result.txt.

Plik place.txt powinien zawierać dokładnie jeden wiersz, w którym zapisano współrzędne (poziomą i pionową) miejsca znalezienia planu. Musisz utworzyć własny plik wejściowy under.inp. Plik result.txt będzie składał się z dwóch wierszy. W pierwszym wierszu znajdą się argumenty x i y wywołanej przez Ciebie procedury finish (x,y). Drugi wiersz będzie zawierał komunikat postaci "You used look nnn times", co się tłumaczy na "Użyłeś look nnn razy". Pamiętaj, że służy to tylko sprawdzeniu zgodności twojego programu z biblioteką. Nie ma to nic wspólnego z poprawnością Twojego rozwiązania.