Potyczki Informatyczne Nowej Generacji v2.0

Zadanie eliminacyjne w konkursie WIPING2 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Kwadratowa krzyżówka

Wyobraź sobie krzyżówkę, w której jest tyle samo kolumn i wierszy. I wiersze, i kolumny numerowane są od 1. Krzyżówkę tę będziesz wypełniał słowami, co czasem może okazać się niewykonalne. Słowa wpisuje się do krzyżówki począwszy od kratki leżącej we wskazanym wierszu i kolumnie oraz we wskazanym kierunku (pionowo albo poziomo). Wpisanie słowa jest udane, jeśli słowo zmieści się w całości w krzyżówce i jeśli żadna z liter tego słowa nie koliduje z literami słów wpisanych do krzyżówki wcześniej.

Twoim zadaniem będzie napisanie programu, który stwierdzi, czy wskazany zbiór słów da się wpisać do przykładowej krzyżówki. 

Przygotuj się więc do napisania programu, który otrzyma na wejściu:

1. liczbę całkowitą n (1 <= n <= 100)  opisującą rozmiar jednego boku krzyżówki (liczbę kratek)
   
2. nieznaną z góry liczbę słów, które powinny zostać wpisane do krzyżówki
   

Twoim zadaniem jest wyprowadzenie na wyjście liczby słów, które udało się wpisać do krzyżówki (zakładamy, że pierwsze niepowodzenie ostatecznie przerywa nasze działanie).

Wejście

Kolejno:

• rozmiar boku krzyżówki z przedziału <1..100>
• nieznana z góru liczba wierszy, a w każdym z nich kolejno:
  • w - numer wiersza, od którego zaczyna się wpisywane słowo
  • k - numer kolumny, od której zaczyna się wpisywane słowo
  • d - kierunek wpisywania (1 - pionowo, 2 - poziomo)
  • s - wpisywane słowo (spójny ciąg małych liter alfabetu łacińskiego)
    

Wyjście

Jeden wiersz tekstu zawierający liczbę całkowitą informującą ile słów udało się wpisać do krzyżówki do chwili pierwszego niepowodzenia.

Przykład

Wejście:

2

1 1 2 ab

2 1 2 cd

Wyjście:

2

Wejście:

2

1 1 2 ab

1 1 1 ba

Wyjście:

1

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwiązanie daje 10% punktacji zadania

• zadanie ma wartość punktową 3,0