POLSKI SPOJ

Zadanie polega na napisaniu programu sterującego postacią -- graczem, który poszukuje wyjścia z labiryntu. Komunikacja z systemem ma charakter interaktywny: program wypisuje polecenia (oznaczane w treści na niebiesko) i otrzymuje informacje i komunikaty zwrotne od systemu (oznaczane w treści na czerwono).

Zasady

Struktura labiryntu. Labirynt złożony jest z pól pustych (znak '.') i elementów ściany (znak 'X'). Dokładnie jeden element ściany zewnętrznej, otaczającej cały labirynt, jest oznaczony jako wyjście (znak 'E'). Pozycja gracza to wyróżnione puste pole (znak 'O'). Można przyjąć, że ściany mają charakter eleganckiego muru, tzn. każdy element ściany sąsiaduje wzdłuż krawędzi z co najwyżej 2 innymi elementami ściany, a elementy ściany stykające się rogami muszą mieć wspólnego sąsiada po krawędzi. W labiryncie panuje zupełna ciemność, a gracz nie posiada mapy.

Rozpoczęcie gry. Gracz znajduje się początkowo w nieznanym miejscu na pustym polu wewnątrz labiryntu. Ma przy sobie pochodnię i pewną ilość dynamitu (n >= 0), o czym informuje komunikat powitalny systemu:

You wake up with a headache, completely lost in a dark maze.
In your pockets you find a torch and n stick[s] of dynamite.

Dozwolone czynności. Gracz może poruszać się po labiryncie, użyć pochodni lub dynamitu, wydając jedno z następujących poleceń (do realizacji "podstawowej" funkcjonalności wystarczą tylko pierwsze dwa z nich):

• walk (north|south|east|west) k - powoduje przemieszczenie gracza w wybranym kierunku o k pól. Każde pole, przez które przechodzi gracz, musi być puste lub wyjściem z labiryntu. Komunikat zwrotny systemu brzmi:
  • You are still lost in a dark maze. - w przypadku nieznalezienia wyjścia
  • Against all odds, you have found the exit. Congratulations! - w przypadku wkroczenia na pole oznaczone 'E' (rozgrywkę uważa się za zakończoną - sukces)
• look around - powoduje oświetlenie 8 pól bezpośrednio otaczających gracza i odpowiedni komunikat zwrotny systemu, np.:
  The maze around you looks like this:
  X.X
  .OX
  .XX
• look (north|south|east|west) k - polecenie analogiczne do 'look around', przy czym widok we wskazanym kierunku będzie miał zasięg k (zamiast 1). W przypadku, gdy w wierszu/kolumnie gracza znajduje się ściana zasłaniająca widok, dalsze pola nie będą wyświetlane. Przykładowy komunikat zwrotny dla polecenia 'look north 4' może wyglądać następująco:
  The maze around you looks like this:
  .XX
  ..X
  X..
  X.X
  .OX
  .XX
  W tym przypadku polecenie 'look north 10' dałoby identyczny efekt ze względu na zasłaniającą od góry ścianę.
• use dynamite - polecenie powoduje zastąpienie 8 pól sąsiadujących z graczem przez pola puste, bez skutków ubocznych dla gracza (ale kosztem zmniejszenia o 1 posiadanej ilości dynamitu). Komunikat zwrotny systemu ma następującą postać:
  You light up a stick of dynamite.
  The explosion knocks you to the ground, but amazingly you survive.

Ograniczenia. W jednej rozgrywce liczba wydawanych do systemu poleceń nie może przekroczyć 10⁴. Należy też oszczędzać zasoby (umownie: ilość zużytego tlenu nie może przekroczyć 10⁷, przy czym przejście 1 pola kosztuje 10 jednostek tlenu, użycie pochodni kosztuje 1 jednostkę tlenu za każde oświetlone pole, użycie dynamitu kosztuje 1000 jednostek tlenu). W przypadku przekroczenia któregoś z ograniczeń lub naruszenia zasad (uderzenie w ścianę, próba użycia nadmiernej ilości dynamitu, wydanie nieprawidłowego polecenia), system wypisuje komunikat zwrotny typu STOP. Opis problemu., a rozgrywkę uważa się za zakończoną.

Wejście/Wyjście

W jednym uruchomieniu programu realizujemy pewną liczbę t (t < 20) rozgrywek w różnych labiryntach. Na początku system podaje wartość t, po czym nastąpują po sobie wszystkie rozgrywki zgodnie z opisaną wcześniej specyfikacją.

Program po wypisaniu każdej linii powinien opróżniać bufor wyjściowy poleceniem fflush (stdout), bądź też na początku wykonania ustawić odpowiedni tryb buforowania, np. setlinebuf (stdout).

Przykład scenariusza można znaleźć tutaj.

Dane testowe

Funkcjonalność za 0-2pkt. Labirynt mieści się w tablicy 50x50 i składa się tylko ze ściany zewnętrznej. Żadne pole labiryntu nie jest położone na północ lub na zachód od gracza. Wystarcza użycie poleceń 'walk ... 1' i 'look around', dynamitu brak.

Funkcjonalność za 2-5pkt. Labirynt mieści się w tablicy 50x50. Wystarcza użycie poleceń 'walk ... 1' i 'look around', dynamitu brak. Przykładowa strategia opisana jest poniżej.

Funkcjonalność za 5-7pkt. Labirynt mieści się w tablicy 500x500. Ściany labiryntu złożone są z co najwyżej 500 odcinków, a ich łączna długość nie przekracza 2500. Wystarcza użycie poleceń 'walk ... 1' i 'look around', dynamitu brak.

Funkcjonalność za 7-8pkt. Labirynt mieści się w tablicy 5000x5000. Ściany labiryntu złożone są z co najwyżej 500 odcinków, a ich łączna długość nie przekracza 25000. Dynamitu brak.

Funkcjonalność za 8-9pkt. Labirynt mieści się w tablicy 50000x50000. Ściany labiryntu złożone są z co najwyżej 500 odcinków, a ich łączna długość nie przekracza 250000. Dynamitu brak.

Funkcjonalność za 9-10pkt. Labirynt mieści się w tablicy 50000x50000. Ściany labiryntu złożone są z co najwyżej 500 odcinków, a ich łączna długość nie przekracza 250000. Dynamit co prawda jest, ale tylko w takiej ilości, jakiej naprawdę potrzeba.

Przykładowa strategia - przeszukiwanie wgłąb (do 5pkt.)

DFS:
jeżeli ( bieżące pole to wyjście ) wyjdź z programu;
zaznacz bieżące pole jako odwiedzone;
wypisz 'look around';
wczytaj informacje o sąsiedztwie;
dla każdego direction ze zbioru {'west', 'north', 'east', 'south'}
jeżeli ( pole w kierunku direction nie zostało jeszcze odwiedzone i nie jest ścianą )
{
wypisz 'walk direction 1';
uruchom rekurencyjnie DFS;
wypisz 'walk przeciwnie do direction 1';
}

Przykładowa strategia - omijanie przeszkód (do 10pkt.)

Pseudokod mniej szczegółowy; wynik zależny jest od sposobu implementacji. Ustalamy arbitralnie jeden kierunek (np. północny) i próbujemy się w nim poruszać.

iteracyjnie wykonuj:
jeżeli ( można iść na północ ) idź na północ;
w przeciwnym razie
{
spróbuj obejść wokół napotkanej przeszkodę.
jeżeli ( przeszkody nie da się obejść, tzn. gracz jest uwięziony w środku )
zastosuj dynamit.
w przeciwnym razie umieść gracza przy krańcu przeszkody
najdalej wysuniętym na północ.
}

Sędzia

Do testowania programów może się przydać arbiter wykorzystywany w zadaniu. Tutaj można pobrać kod źródłowy dla kompilatora g++ (system Unix/Linux lub Cygwin dla Windows).

Typowe uruchomienie może wyglądać następująco (oczywiście w systemie SPOJ odbywa się to zupełnie inaczej):

ppp07d-judge input_file tested_program - testowanie programu grającego (wyniki na ekranie)
ppp07d-judge input_file tested_program 2> log_file - testowanie programu grającego (wyniki w pliku logu)
ppp07d-judge input_file 2> /dev/null - ręczna rozgrywka z arbitrem

gdzie: input_file - plik z opisem labiryntów, tested_program - ścieżka do pliku wykonywalnego programu grającego.

Format pliku input_file jest następujący: najpierw t, liczba rozgrywek. Dla każdej rozgrywki, pierwsza linia zawiera 6 liczb całkowitych: liczbę odcinków ścian k, położenie x i y wyjścia, początkowe położenie x i y gracza, ilość n dostępnego dynamitu. Każda z kolejnych k linii zawiera opis jednego odcinka ściany w postaci 4 liczb całkowitych x1 y1 x2 y2, gdzie x1<=x2 i y1<=y 2, a przynajmniej jeden z tych warunków powinien być równością. Plik wejściowy odpowiadający przykładowi z treści zadania jest dostępny tutaj.