Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SAPER - Saper

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.

W zadaniu jest 10 testów, maksymalnie można zdobyć 10 punktów. Zadanie zaakceptowane zostanie, gdy uzyskasz co najmniej 3 punkty. Po wysłaniu zgłoszenia jest możliwość podglądu wyniku sędziego.

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.

Dodane przez:Mariusz Śliwiński
Data dodania:2015-07-29
Limit czasu wykonania programu:1s-5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.