Gra toczy się na planszy o wymiarach NxM (pola indeksujemy od 1, startując od lewego, górnego rogu). Na jednym z pól stoi CosmoSkoczek. Dwaj gracze na przemian wykonują ruchy, polegające na przesunięciu CosmoSkoczka o X pól w lewo i Y pól do góry. Listę dopuszczalnych ruchów gracze ustalają na początku rozgrywki. Przegrywa gracz, który nie może wykonać ruchu. Dodatkowo niektóre pola na planszy są dziurawe. Jeśli CosmoSkoczek stanie na dziurawym polu po raz K-ty w danej grze to gracz, który go tam ustawił, przegrywa. Aby nie było zbyt trudno na planszy znajdują się też HiperTeleporty. Jeśli gracz przesunie pionek na HiperTeleporta może (ale nie musi) wykonać dodatkowy ruch.
Napisz program, który dla każdej z danych początkowych pozycji CosmoSkoczka określi, czy gracz rozpoczynający może wygrać niezależnie od posunięć drugiego.
W pierwszym wejściu mamy kolejno: N - liczbę wierszy i M - liczbę kolumn planszy, liczbę K oraz liczbę dostępnych ruchów - T. W następnych T wierszach zapisane są pary liczb naturalnych X i Y. Każda taka para oznacza, że w jednym ruchu CosmoSkoczka można przesunąć o X w lewo i o Y do góry. W kolejnych N wierszach zapisana jest plansza. Kropka symbolizuje normalne pole, litera H - HiperTeleporta, D - dziurę. Następnie mamy kilka początkowych pozycji CosmoSkoczka (kolejno nr wiersza i kolumny), dla których mamy stwierdzić czy gracz rozpoczynający grę ma strategię wygrywającą. Dane wejściowe kończą się liczbą 0.
Dla każdej pozycji początkowej CosmoSkoczka należy wypisać TAK lub NIE zależnie od tego, czy pierwszy gracz ma strategię wygrywającą.
Dla danych wejściowych:
3 5 2 2 1 1 2 1 D.... .D.H. ..... 2 1 3 3 3 4 3 5 0
poprawnym wynikiem jest:
NIE TAK TAK TAK
Możesz założyć, że początkowo CosmoSkoczek stoi na normalnym polu. Liczby N, M i T będą nie większe niż 100. Liczba K będzie nie większa niż 10^9.
[Zgłoś rozwiązanie] [Moje zgłoszenia]