To zadanie jest interaktywne.
Taja potrafi łatwo wygrać w tę grę, ale jej przyjaciele nie. Teraz oferuje Ci możliwość zagrania w nią.
Wyposażenie gry składa się z planszy $n \times n$ ($5 \le n \le 40$), pionka, dwóch monet (COIN1, COIN2), dwóch kostek z kierunkami świata (DICE1, DICE2) oraz wielu bloków o rozmiarze jednej komórki.
| Nazwa | Liczba ścian | Ściany |
|---|---|---|
| COIN1. Moneta ruchu | 2 | SLIDE, RAM |
| COIN2. Moneta modyfikacji | 2 | PLACE, REMOVE |
| DICE1. Pierwsza kostka z kierunkami | 4 | N (Północ), S (Południe), W (Zachód), E (Wschód) |
| DICE2. Druga kostka z kierunkami | 8 | N (Północ), S (Południe), W (Zachód), E (Wschód), NW (Północny zachód), NE (Północny wschód), SW (Południowy zachód), SE (Południowy wschód) |
Przed rozpoczęciem gry pionek i niektóre bloki są umieszczone na planszy. Następnie gracz wykonuje ruchy. Najpierw gracz wybiera monetę i rzuca nią, aby określić akcję. Następnie wybiera jedną z kostek i rzuca nią, aby określić kierunek $dir$. Po tym następuje jedna z czterech akcji:
| Akcja | Opis |
|---|---|
| SLIDE | Przesuń pionek przez puste komórki w kierunku $dir$, aż pionek zderzy się z blokiem lub krawędzią planszy |
| RAM | Przesuń pionek przez puste komórki w kierunku $dir$, aż zderzy się z pierwszym blokiem. Następnie przesuń pionek i blok w tym samym kierunku, aż przesuwany blok zderzy się z innym blokiem lub krawędzią planszy |
| PLACE | Jeśli sąsiednia komórka w kierunku $dir$ obok pionka jest pusta i znajduje się na planszy, umieść blok na tej komórce |
| REMOVE | Jeśli sąsiednia komórka w kierunku $dir$ obok pionka zawiera blok i znajduje się na planszy, usuń blok z tej komórki |
Celem jest umieszczenie pionka na komórce końcowej.
Jedno zapytanie w tym zadaniu to jeden rzut monetą i jeden rzut kostką.
Interakcja
Na początku interaktor podaje rozmiar labiryntu, labirynt oraz współrzędne komórki końcowej. Następnie wykonywane są następujące 4-etapowe akcje:
- Program jury wyświetla współrzędne pionka lub informuje, że pionek dotarł do komórki końcowej.
- Twój program wyświetla nazwę monety.
- Program jury wyświetla nazwę akcji wylosowanej na monecie.
- Twój program wyświetla nazwę kostki.
- Program jury wyświetla nazwę kierunku wylosowanego na kostce oraz dodatkowe informacje dla akcji "RAM".
Wyjście
Standardowe wyjście powinno składać się z pary linii: nazwa monety i nazwa kostki. Nazwa monety to ciąg znaków "COIN1" lub "COIN2". Nazwa kostki to ciąg znaków "DICE1" lub "DICE2".
Nie zapomnij opróżnić bufora standardowego wyjścia po wypisaniu każdej linii.
Wejście
Pierwsza linia standardowego wejścia zawiera jedną liczbę całkowitą $n$ — rozmiar labiryntu. Następne $n$ linii zawiera $n$ znaków "." (ASCII 46) lub "#" (ASCII 35), oznaczających odpowiednio pustą komórkę i komórkę z blokiem.
Następna linia zawiera dwie liczby całkowite $r_f$ i $c_f$ — numer wiersza i numer kolumny komórki końcowej. Lewy górny róg to $(1, 1)$, prawy dolny to $(n, n)$. Komórka końcowa i początkowa są puste.
Kolejne grupy opisują każdy ruch:
- Pierwsza linia grupy zawiera dwie liczby całkowite $r, c$ — numer wiersza i numer kolumny pionka, lub $(-1, -1)$, jeśli pionek dotarł do komórki końcowej.
- Następna linia zawiera nazwę akcji pokazaną na monecie.
- Następna linia zawiera nazwę kierunku pokazaną na kostce.
- Jeśli bieżącą akcją jest "RAM", kolejne dwa ciągi znaków zawierają dwie liczby całkowite $r_1, c_1$ oraz $r_2, c_2$, oznaczające, że pionek zderza się z blokiem o współrzędnych $(r_1, c_1)$ i przesuwa ten blok do komórki $(r_2, c_2)$.
Kierunek północny odpowiada malejącemu numerowi wiersza. Południowy — rosnącemu numerowi wiersza. Kierunek zachodni odpowiada malejącemu numerowi kolumny. Wschodni — rosnącemu numerowi kolumny.
Każda strona monety lub kostki wypada z takim samym prawdopodobieństwem.
Przykład
Wejście 1
5 #.... ..... ..... ..... ..#.. 4 3 1 5 PLACE W 1 5 RAM S 6 5 6 5 5 5 RAM W 5 3 5 1 5 2 PLACE NE 5 2 RAM NE 4 3 2 5 3 4 REMOVE NE 3 4 PLACE S 3 4 SLIDE W 3 1 RAM S 5 1 5 1 4 1 SLIDE E -1 -1
Wyjście 1
COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN2 DICE2 COIN1 DICE2 COIN2 DICE2 COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN1 DICE1
Stan początkowy labiryntu dla przykładu:
Reprezentacja ścieżki jest pokazana poniżej:
