Pionek [B]
Limit pamięci: 192 MB
Rosnąca popularność bajtockich szachów spowodowała, że powstało wiele odmian
tej gry.
Ponieważ w tradycyjnej postaci gra toczy się na nieskończonej planszy, co
bywa kłopotliwe, czasem gra się w uproszczone wersje, w których rozmiary
plansz ograniczone są przez .
Niektóre pola planszy są czarne, zaś pozostałe - białe, jednak
sposób pokolorowania pól zależy od konkretnej planszy.
Pionek porusza się na tej planszy w nieco inny sposób niż w szachach
klasycznych - w każdym ruchu może się on przesunąć w pionie, w poziomie lub na skos
na dowolne spośród ośmiu sąsiednich pól, o ile jest ono tego samego koloru
co pole, na którym się aktualnie znajduje.
Przykłady dozwolonych ruchów.
Dla podanych par pól na planszy należy stwierdzić, czy pionek może
przejść pomiędzy nimi.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite
, i (, ,
), pooddzielane pojedynczymi odstępami i oznaczające
odpowiednio rozmiar planszy, liczbę czarnych fragmentów planszy
opisanych na wejściu oraz liczbę zapytań.
Plansza ma wymiary i składa się z pól, których obie
współrzędne są z przedziału od do .
W kolejnych wierszach znajdują się opisy czarnych obszarów planszy
(nie muszą one być koniecznie rozłączne).
Każdy z nich składa się z trzech liczb całkowitych ,
oraz (, ),
pooddzielanych pojedynczymi odstępami i oznaczających, że w wierszu
pola w kolumnach od do są czarne.
Pola planszy, które nie są zawarte w żadnym czarnym obszarze opisanym
w wejściu, są białe.
W kolejnych wierszach znajdują się zapytania.
Każde zapytanie składa się z dwóch par liczb całkowitych
, , ,
()
pooddzielanych pojedynczymi odstępami.
Oznaczają one pytanie o możliwość przejścia z pola w wierszu
i kolumnie na pole w wierszu i kolumnie
.
Wyjście
Na standardowe wyjście należy wypisać wierszy z odpowiedziami
na poszczególne zapytania, w takiej samej kolejności, w jakiej
występują one na wejściu.
Odpowiedź na każde zapytanie to wiersz z napisem "TAK"
lub "NIE" (bez cudzysłowów), w zależności od tego, czy
pionek może przejść pomiędzy dwoma podanymi polami, nie przechodząc
nigdy przez pole innego koloru.
Przykład
Dla danych wejściowych:
4 5 2
1 1 1
2 3 4
3 2 2
4 2 2
4 2 2
1 1 3 2
1 2 4 4
poprawną odpowiedzią jest:
NIE
TAK
Przykładowa plansza wraz z zapytaniami.
Autor zadania: Krzysztof Diks.