Muszę otworzyć dziś drzwi, za którymi znajduje się coś specjalnego. W ręku mam zestaw kluczy - co najmniej jednym z nich mogę je otworzyć. Niestety jest ciemno i jestem prawie pewien, że klucz, który będzie pasował, wybiorę jako ostatni. Sprawdź to!
W pierwszym wierszu znajdują się liczby n i m określające wymiary macierzy przedstawiającej zamek (n < 101, m < 101). Macierz składa się wyłącznie z zer i jedynek. Zbiór jedynek oznacza, że w tym miejscu jest dziurka. W zamku jest tylko jedna dziurka do klucza oraz co najmniej jedna jedynka.
Następnie n wierszy po m kolumn reprezentujących zamek.
W kolejnym wierszu jedna niewielka liczba określająca liczbę kluczy do sprawdzenia.
Specyfikacja każdego klucza (klucz zdefiniowany jest w pewnym układzie współrzędnych, który może być obrócony o krotność dziewięćdziesięciu stopni):
W pierwszym wierszu jedna liczba w określająca ilość współrzędnych klucza (w < 10001).
W kolejnych w wierszach po dwie współrzędne x i y, takie że |x| < 1000, |y| < 1000. Współrzędne są unikatowe i nie są posortowane.
Dla każdego klucza napis pasuje lub napis nie pasuje w zależności od sytuacji.
Uwaga! Klucz musi idealnie pasować do dziurki - każda 'jedynka' z zamka musi mieć odpowiadającą sobie współrzędną klucza (być może obróconego).
Wejście: 6 7 0000000 0011100 0110110 0011100 0001100 0000000 2 10 0 2 -1 1 0 1 1 1 -2 0 -1 0 1 0 -2 -1 -1 -1 0 -1 12 0 2 -1 1 0 1 1 1 -2 0 -1 0 1 0 -2 -1 -1 -1 0 -1 1 -1 0 -2 Wyjście: nie pasuje pasuje
Przykładowe rozwiązanie. „Wycinamy” prostokąt w którym znajduje się klucz. Wykonujemy jego cztery wersje, obracając każdą o kolejne 90 stopni. Dla danego układu współrzędnych reprezentujących klucz wykonujemy translację do pierwszej ćwiartki tak, aby najbardziej wysunięty punkt na lewo leżał na osi OX a najbardziej wysunięty punkt w dół leżał na osi OY. W ostatnim kroku dopasowujemy wycięty prostokąt we wszystkich czterech wersjach do układu współrzędnych.