|
|||||||||||||||
|
REKURENCYJNA MRÓWKA
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.
Rysunek 1
ZadanieNapisz program, który:
WejścieW 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ścieW 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ładDla 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 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.
|