IV Olimpiada Informatyczna 1996/97
|
Zadanie: REK
|
Autor: Wojciech Rytter
|
Zawody II stopnia |
Plik źródłowy: | REK.??? (np. pas, c, cpp) |
Plik wykonywalny: | REK.exe |
Plik wejściowy: | REK.in |
Plik wyjściowy: | REK.out |
Mrówka ma obejść wszystkie pola szachownicy 2n x 2n poza polami zabronionymi - każde pole dokładnie jeden raz. Obchodzenie musi się zacząć w polu startowym leżącym w lewym górnym rogu i zakończyć na polu leżącym na brzegu szachownicy (mrówka na końcu opuszcza szachownicę). Zakładamy, że pole startowe nie jest zabronione. W jednym kroku mrówka może przejść do jednego z co najwyżej czterech sąsiednich pól szachownicy (w górę, dół, lewo lub prawo).
Mrówka obchodzi szachownicę w sposób w pewnym sensie rekurencyjny: aby obejść kwadrat 2k x 2k dzieli go na cztery części (rekurencyjne ćwiartki) o rozmiarach 2k-1 x 2k-1, a następnie obchodzi każdą z nich, to znaczy, jeżeli mrówka wejdzie do jednej z ćwiartek, to może z niej wyjść dopiero wtedy, gdy obejdzie wszystkie nie zabronione pola w tej ćwiartce.
Rysunek 1 przedstawia dwie trasy rekurencyjnej wędrówki mrówki na szachownicy o rozmiarach 23 x 23, od pola startowego (0,0) do pola leżącego odpowiednio na górnym oraz lewym brzegu szachownicy.
W drugim wierszu jest zapisana liczba pól zabronionych m <= 50.
W każdym z kolejnych m wierszy jest zapisana para liczb całkowitych nieujemnych i, j oddzielonych pojedynczym odstępem, są to dwie współrzędne: numer wiersza i oraz numer kolumny j odpowiedniego zabronionego pola. Wiersze szachownicy numerujemy od góry w dół, a kolumny od lewej do prawej, od 0 do 2n-1.
3 15 2 0 1 0 3 0 6 0 7 0 6 1 7 1 6 2 7 2 6 3 7 3 0 2 0 3 0 6 0 7 1 6 1 7poprawnym rozwiązaniem jest plik REK.OUT
0 4 NIE NIE 4 0
Twój program powinien szukać pliku REK.IN w katalogu bieżącym i tworzyć plik REK.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę REK.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku REK.EXE.