The puzzle game Slitherlink is played on a grid. Each cell of the grid contains either a space or an integer from 0 to 3. The goal is to draw in some grid lines connecting vertically or horizonally adjacent points on the grid subject to the following constraints:
Determining if a given instance of a Slitherlink puzzle can be completed or not is NP-complete which means nobody knows of an efficient algorithm to solve the problem for large grids. Your task is simpler. Given an instance of a Slitherlink puzzle and a proposed solution, you are to check that the solution indeed satisfies the constraints for that puzzle.
For example, the first sample input is not valid since there are 2 grid lines drawn adjacent to a cell numbered 1. The second, third, and fourth samples are invalid since the grid lines do not form a single loop. However, the fifth sample is valid.
The first integer denotes the number of test cases to follow. Each test case is specified by a line containing two positive integers R and C (both at most 50) followed by a grid of 2R+1 rows of 2C+1 characters. The contents of row r and column c (counting from 1) are as follows:
You can assume all inputs are well-formed descriptions of a Slitherlink puzzle and a proposed solution. A blank line also precedes each test case.
The output for each test case is a single line containing either Valid
or Invalid
, depending on whether the proposed
solution is valid or not.
5 3 3 + +-+ + 1| |2 +-+ +-+ | 1 | +-+-+ + 1 |3| + + +-+ 2 3 +-+ +-+ |3| |3| + + + + |3| |3| +-+ +-+ 2 2 +-+-+ |3|3| + + + |3|3| +-+-+ 2 2 + +-+ 2| | +-+-+ | |2 +-+ + 3 4 + +-+-+ + | |2 +-+ + +-+ |3 0 3| +-+ +-+-+ | | 1 + +-+ + +
Invalid Invalid Invalid Invalid Valid