În această problemă vrem să verificăm dacă un caroiaj este sau nu _labirint_. Un labirint este un caroiaj cu o serie de proprietăţi suplimentare:
* celulele adiacente pe verticală sau orizontală pot avea maxim un perete despărţitor, definit în reprezentarea uneia din celule,
* fiecare celulă de pe margine are pereţi care despart caroiajul de exterior pe fiecare latură cu exteriorul,
* există exact un drum simplu format din paşi pe orizontală şi verticală între celule adiacente şi nedespărţite de perete, între oricare două celule din caroiaj.
* celulele adiacente pot avea maxim un perete despărţitor, definit pentru doar una din celule,
* fiecare celulă de pe margine e despărţită de exterior prin perete,
* între oricare două celule din caroiaj există **exact** un drum simplu format din paşi pe orizontală şi verticală între celule adiacente şi nedespărţite.
Fiecare celulă este codificată ca un întreg pe $4$ biţi, unde biţii adevăraţi denotă, în ordine, existenţa unui perete pe direcţiile sus, dreapta, jos, stânga.
Numărul $5$, de exemplu, poate fi scris ca $0$ $×$ $2^3^$ + $1$ $×$ $2^2^$ + $0$ $×$ $2^1^$ + $1$ $×$ $2^0^$ şi reprezintă o celulă cu pereţi în dreapta şi stânga.
Fiecare celulă este descrisă de un număr natural pe $4$ biţi, unde biţii adevăraţi descriu, în ordine, existenţa unui perete pe direcţiile sus, dreapta, jos, stânga. De exemplu, numărul $5$ = $0$ $×$ $2^3^$ + $1$ $×$ $2^2^$ + $0$ $×$ $2^1^$ + $1$ $×$ $2^0^$ descrie o celulă cu pereţi doar în dreapta şi stânga.
h2. Date de intrare
În fişierul de intrare $verlab.in$ sunt date numerele $r$ şi $c$, dimensiunile caroiajului: linii şi apoi coloane.
Acestea sunt urmate de $r$ $×$ $c$ numere între $0$ şi $15$, reprezentând celulele pe rânduri şi coloane. Numerele sunt precedate, separate şi urmate de oricâte caractere albe.
Primul număr din fişierul de intrare $verlab.in$ este numărul de teste $T$. Apoi pentru fiecare test, se dau numărul de linii $R$ şi numărul de coloane $C$; acestea sunt urmate de $R$ $×$ $C$ numere între $0$ şi $15$, reprezentând celulele pe rânduri şi coloane. Numerele sunt date: de sus în jos şi, pentru un rând fixat, de la stânga la dreapta. Numerele sunt precedate, separate şi urmate de oricâte caractere albe.
h2. Date de ieşire
În fişierul de ieşire $verlab.out$ se găseşte un singur număr: $1$ pentru un caroiaj care este labirint, sau $0$ pentru un caroiaj care nu este labirint. Numărul este urmat de caracterul sfârşit de linie.
În fişierul de ieşire $verlab.out$ se găsesc $T$ numere, câte un singur număr pentru fiecare test, în ordinea testelor: $1$ pentru un caroiaj care este labirint, sau $0$ pentru un caroiaj care nu este labirint. Numărul este urmat de caracterul sfârşit de linie.
h2. Restricţii
* $1$ $<=$ $r$, $c$ $<=$ $1.000$
* $1$ $<=$ $R$, $C$, $T$ $<=$ $100$
h2. Exemplu
table(example). |_. verlab.in |_. verlab.out |
| 2 2
| 2
2 2
13 12
3 6
1 1
14
| 1
|
0
|
h3. Explicaţie
Caroiajul are $4$ celule, distribuite pe $2$ rânduri şi $2$ coloane. Celula din stânga sus cu valoarea $13$ are trei pereţi: în sus, dreapta şi stânga. Celula din dreapta sus cu valoarea $12$ are doi pereţi: în sus şi în dreapta. Celula din dreapta jos cu valoarea $6$ are doi pereţi: în dreapta şi în jos. Celula din stânga jos cu valoarea $3$ are doi pereţi: în jos şi în stânga. De observat cum peretele drept al celulei din stânga sus o desparte pe aceasta de celula din dreapta sus.
În primul test, caroiajul are $4$ celule, distribuite pe $2$ rânduri şi $2$ coloane. Celula din stânga sus cu valoarea $13$ are trei pereţi: în sus, dreapta şi stânga. Celula din dreapta sus cu valoarea $12$ are doi pereţi: în sus şi în dreapta. Celula din dreapta jos cu valoarea $6$ are doi pereţi: în dreapta şi în jos. Celula din stânga jos cu valoarea $3$ are doi pereţi: în jos şi în stânga. De observat cum peretele drept al celulei din stânga sus o desparte pe aceasta de celula din dreapta sus. Caroiajul respectă proprietăţile de labirint. În al doilea test, singurei celule din caroiaj îi lipseşte unul din pereţii cu exteriorul, ceea ce face caroiajul să nu fie un labirint.
== include(page="template/taskfooter" task_id="verlab") ==
