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_20_09 - Stawy i grobla

Stawy i grobla

Łamigłówka stawy i grobla znana także pod nazwą nurikabe, to łamigłówka pochodząca od wydawnictwa Nikoli. Początkowo diagram w niektórych polach zawiera liczby, które są częścią stawu złożonego z tylu pól, jaka jest wartość tej liczby. Wszystkie stawy są wielobokami rozdzielonymi groblą, która tworzy jedną spójną figurę. Częścią grobli nie może być kwadrat złożony z czterech pól 2×2. Zadanie polega na takim zaczernieniu pól tworzących groblę, aby powstałe w ten sposób stawy były rozłączne, tzn. nie były połączone bokami. Twoim zadaniem jest rozstrzygnąć, na podstawie podanego diagramu, czy łamigłówka jest rozwiązana, czy też nie. Każdy diagram opisany jest za pomocą znaków x i . oraz liczb z przedziału [1-9]. Znak x oznacza pole zaczernione należące do grobli, liczby od 1 do 9 to pola, które są częścią stawu, o których mowa wyżej, a znak .(kropka) jest polem niezaczernionym należącym do stawu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (d ≤ 100). Każdy przypadek opisują w pierwszym wierszu dwie liczby całkowite m, n (4 ≤ m,n ≤ 100) oznaczające wymiary diagramu. Dalej podanych jest n wierszy, każdy po m znaków opisujących diagram według specyfikacji podanej w treści zadania. Należy założyć, że wszystkie diagramy podane na wejściu są poprawne.

Wyjście
Dla każdego przypadku testowego należy wypisać TAK albo NIE, w zależności czy łamigłówka jest rozwiązana, czy też nie.

Przykład

Wejście

3
6 5
2.xxx1
xxx.xx
x3x2x.
x..xx.
xxxx4.
6 5
2.xxx1
xxx.xx
x3x2x.
...xx.
xxxx4.
6 5
2.xxx1
xxx..x
x3x3x.
x..xx.
xxxx4.

Wyjście
TAK
NIE
NIE


Dodane przez:Mariusz Śliwiński
Data dodania:2014-12-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-12-27 20:16:49 Tomek Weso³owski
Dzięki!
2014-12-27 20:05:46 Mariusz ¦liwiñski
Tak, staw musi zawierać liczbę. Najważniejsze jednak w łamigłówce jest, aby grobla stanowiła jedną spójną całość, inaczej łamigłówka nie jest rozwiązana. Dodałem jeden przypadek, w którym nie jest spełniony ten warunek.
2014-12-27 19:56:53 Tomek Weso³owski
Łamigłówka nie jest ułożona, wtw:
- zawiera zaczerniony kwadrat 2x2,
- liczba na polu nie zgadza się z wielkością stawu
- są 2 cyfry na jednym stawie?

Czy na każdym stawie musi być jakaś cyfra?
2014-12-27 19:29:45 Mariusz ¦liwiñski
Przypadki testowe zawierają cztery zaczernione pola 2x2, wówczas łamigłówka nie jest ułożona i trzeba wypisać NIE.

Pisząc, że diagramy podane na wejściu są poprawne miałem na myśli, że gdyby usunąć z nich wszystkie zaczernione pola, diagram da się ułożyć.
2014-12-27 19:25:29 Mariusz ¦liwiñski
Nie, to jest wbrew regułom, każdy staw musi zawierać jedną liczbę.
2014-12-27 19:24:38 Tomek Weso³owski
Należy założyć, że wszystkie diagramy podane na wejściu są poprawne. - czyli nie zawierają zaczernionego kwadratu 2x2?
2014-12-27 19:21:39 Tomek Weso³owski
Czy staw może zawierać dwa pola z cyfrą?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.