916 . Pipe Puzzle
Description
On a R*C grid, each cell contains a pipe pattern that is one of the follwing:
Now, one can rotate the pattern in each cell (by 0, 90, 180, or 270 degree) to make the puzzle valid. A configuration is VALID if there are no misconnection, that is, two adjacent pattern is either inter-connected with pipe or not connected at all, and no pipe leads to the border.
Given the pattern of each cell on the grid, determine whether it is possible to rotate the patterns and obtain a valid configuration.
Input Format
In the first line a number T is specified, indicating the number of testcases.
In each test case the first line reads the number of rows R and the number of columns C of the grid, respectively.
Following is R line each containing C integer, where each number is either 0, 1, 2, 3, or 4, indicating which kind of pattern is on that cell. (Referring to the number of "outgoing pipes" from that cell. For example if a cell is written "2" then that the cell is occupied by a "L-shaped" pipe.)
Output Format
For each testcase, output "yes"(without brackets) if it is possible to find a valid configuration, or "no" otherwise.
1 <= R,C <= 70
Sample Input 1
2 1 2 2 1 3 4 2 3 2 0 3 4 3 0 2 3 3 1
Sample Output 1
no yes
Hints
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|