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 14:50:01 Bartek
Zgadza się. U mnie jest tak samo.
2015-12-27 14:47:53 Mateusz Radecki
3
2 6 3
...x..
..xx..
2 5 3
..x..
.xx..
2 5 3
...x.
..xx.

TAK
NIE
TAK

??
2015-12-27 14:44:17 Mariusz ¦liwiñski
Kolejne kroki
http://www.mariosoft.pl/1.out
2015-12-27 14:42:43 Mateusz Radecki
Jeśli chodzi o komentarz z 13:55 to mój program zaczął w lewym górnym rogu i dał radę.
2015-12-27 14:39:02 Bartek
A czy mogę prosić o wyjaśnienie testu który ostatnio wrzuciłem ? Albo przynajmniej o koordy pierwszego ruchu.
2015-12-27 14:38:20 Mariusz ¦liwiñski
Zgadza się.
2015-12-27 14:36:02 Bartek
Zgadza się. Mam taki sam wynik.
2015-12-27 14:33:11 Mateusz Radecki
O, można się pokłócić, mam kilka ciekawych testów.

2
9 10 20
x.x...x...
....x..xx.
.....x....
..........
.x........
xx.x......
.xx....x..
.x.xxx....
.....xx...
9 10 21
x.x...x...
....x..xx.
.....x....
..........
.x........
xx.x......
.xx....x..
.x.xxx....
x....xx...

Tutaj wynikiem jest:
TAK
NIE
prawda?

Ostatnio edytowany: 2015-12-27 14:33:38
2015-12-27 14:11:33 Mariusz ¦liwiñski
Dla tego testu: TAK
2015-12-27 13:55:35 Bartek
Czy wynikiem dla tego testu jest NIE ?
1
15 30 38
..............................
...............x....x.........
...........x..x...x...........
..........x..x.....x..........
...........x..x...x...........
.........x.......x............
........x......x...x..........
..........x.......x..x........
.............x...x....x.......
.........x...x......x..x......
...........x...x.x...x........
..........x........x..x.......
.........x....x...x...........
...........x....x.............
..............................
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.