AlgoLiga 2018

Saper

Gra saper

Sprawdź, czy istnieje takie pole diagramu, z którego rozpoczynając, można doprowadzić grę do szczęśliwego jej zakończenia wyłącznie przy pomocy dedukcji.

Twoim zadaniem jest przeprowadzić symulację gry i odpowiedzieć na pytanie postawione wyżej. Na wejściu jako pojedynczy przypadek testowy otrzymasz prostokątny diagram o wymiarach n × m opisany za pomocą dwóch znaków. Znak kropki oznacza wolne pole, a znak x, to pole minowe. Podany diagram służyć ma jako mapa terenu. Program powinien wczytać ją, wyznaczyć pola liczbowe oraz obszary wolne od liczb i trzymać tak zmodyfikowaną mapę w pamięci. Następnie należy sprawdzić, czy startując z pewnego pola diagramu nie należącego do miny, za pomocą dedukcji, można odkryć wszystkie pola nie będące minami.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. Każdy przypadek opisują w pierwszym wierszu trzy liczby całkowite n, m, k (2 ≤ n ≤ 16, 2 ≤ m ≤ 30, 1 ≤ k < n × m) oznaczające kolejno liczbę wierszy i liczbę kolumn diagramu oraz liczbę min. Dalej znajduje się n wierszy, każdy po m znaków, przedstawiające diagram sapera.

Wyjście
Dla każdego przypadku testowego należy wypisać TAK albo NIE jako odpowiedź na postawione pytanie.

Przykład

Wejście
3
3 3 3
...
.xx
.x.
5 5 4
....x
x....
....x
....x
.....
4 7 4
.......
xx...xx
.......
.......

Wyjście
TAK
NIE
TAK

Analiza drugiego przypadku testowego.

5 5 4
....x
x....
....x
....x
.....

Mapa:
11 1x
x1 22
11 2x
   2x
   11

Rozpoczynamy od pustego diagramu.
.....
.....
.....
.....
.....

Jeśli rozpoczniemy np. z pola (1,3) to na podstawie mapy otrzymamy:
.1 1.
.1 2.
11 2.
   2.
   1.

Na lewej bandzie mamy prostą sytuację, z której wnioskujemy, że pole (2,1)
to mina, a pole (1,1) jest wolne. Modyfikujemy diagram zaznaczając minę i
odkrywając pole wolne. Otrzymujemy:
11 1.
x1 2.
11 2.
   2.
   1.

Po prawej stronie diagramu sytuacja jest bardziej złożona. Po poprawnie
przeprowadzonym rozumowaniu możemy być pewni, że pole (3,5) to pole minowe.
Oznaczamy je i otrzymujemy:
11 1.
x1 2.
11 2x
   2.
   1.

Pozostały cztery pola do odkrycia, wśród których są dwie miny. Mamy tu dwie
kombinacje, ale nie dają nam one pewności odkrycia pola nie będącego miną.
Rozpoczynając od nowa z dowolnego innego pola dotrzemy co najwyżej do ostatnio
przedstawionej sytuacji, która nie gwarantuje nam bezpiecznego ukończenia gry.
Odpowiedzą dla tego diagramu jest zatem NIE.