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.|

AL_26_13 - 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.

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-12-23
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

ukryj komentarze
2015-12-27 10:52:27 Bartek
A taki test już zwraca odpowiedź NIE, prawda ?
1
5 5 6
.....
...x.
..xx.
.xx..
....x
2015-12-27 10:25:30 Mariusz ¦liwiñski
Od siebie dodam taki przypadek, odpowiedzią jest TAK

5 5 5
.....
...x.
..xx.
.xx..
.....
2015-12-27 09:42:45 Mariusz ¦liwiñski
Dla tego testu odpowiedzią jest TAK
2015-12-27 09:01:06 Bartek
Jaki jest wynik dla poniższego testu ?
1
5 5 4
....x
..x..
.x...
.....
.x...

@Edit: Złą liczbę min wpisałem w teście :P

Ostatnio edytowany: 2015-12-27 09:36:58
2015-12-26 23:58:22 Mariusz ¦liwiñski
Wszystko jest ok.
2015-12-26 23:43:30 Mateusz Radecki
No teraz to na bank macie źle. :P
2015-12-26 17:14:29 Mariusz ¦liwiñski
Tak, bez tego ani rusz.
2015-12-26 17:11:02 Mateusz Radecki
Czy nasz wirtualny dedukujący gracz, jeśli wydedukuje, że na jakimś polu na pewno nie ma miny, to czy może je kliknąć i poznać liczbę jaka się na nim znajduje?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.