ASCII Labyrinth

We are trying to construct a labyrinth on a board of size m × n. Initially, on each square of the board we find a piece of thin plywood of size 1 × 1 with one of the following three patterns painted on it. While constructing the labyrinth we may turn the pieces arbitrarily but each piece must exactly cover a square of the board. We are not allowed to move a piece to another square of the grid. Given an initial board covered with the pieces, we would like to turn the pieces in such a way that the patterns on the pieces form at least one polygonal curve connecting the top left corner square of the board with the bottom right square of the board. The picture below presents an initial state of a board of size 4 × 6 and a labyrinth constructed from the board in which the above stated goal has been achieved. Your task is to read a description of the initial board with the pieces placed on it and to decide whether one can turn the pieces in such a way that the patterns form a line connecting some edge of the top left square and some edge of the bottom right square of the board. Input The first line of input contains a number c giving the number of cases that follow. The test data for each case start with two numbers m and n giving the number of rows and columns on the board. The remaining lines form an ASCII rendition of the initial board with the pieces placed on squares. The characters used in the rendition are +, -, |, * and space. See the sample input for the format. The size of the input board will be such that m × n ≤ 64. Output For each case print in a single line how many different paths exist in the solutions to the labyrinth problem in the format shown below. Sample Input 1 46 +---+---+---+---+---+---+ ||||||| |||** |** |** |**| | | |||| | +---+---+---+---+---+---+ |||||||

2/2 | |** |** || |* | | ||| ||| +---+---+---+---+---+---+ ||||||| || |||| | ||||||| +---+---+---+---+---+---+ ||||||| |** | || | |* | || | | ||*| +---+---+---+---+---+---+ Sample Output Number of solutions: 2