IV Olimpiada Informatyczna 1996/97

Zadanie: REK
Autor: Wojciech Rytter
REKURENCYJNA MRÓWKA

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.

Trasa mrówki
Rysunek 1

Zadanie

Napisz program, który: Uwaga: każde z czterech pól narożnych należy do dwóch brzegów szachownicy.

Wejście

W pierwszym wierszu pliku tekstowego REK.IN jest zapisana liczba całkowita dodatnia n <= 30.

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.

Wyjście

W każdym z czterech kolejnych wierszy pliku tekstowego REK.OUT należy zapisać dwie liczby całkowite nieujemne oddzielone pojedynczym odstępem - współrzędne (numer wiersza i numer kolumny) odpowiedniego końcowego pola rekurencyjnej trasy mrówki leżącego na: górnym, prawym, dolnym oraz lewym brzegu szachownicy (w takiej kolejności) lub jedno słowo NIE, jeśli takiego pola nie ma.

Przykład

Dla pliku REK.IN będącego opisem szachownicy przedstawionej na rysunku:
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 7
poprawnym 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.