MAZE - The Long and Narrow Maze
Consider a maze consisting of 3 rows of n square blocks each. The passageways in every block match one of three possible patterns, numbered 0 (empty), 1 (straight) and 2 (bent), as depicted below.
Your task is to determine whether it is possible to create a passage in a given maze, with an entrance at the left end and an outlet at the right end of the maze, only by rotating some of the squares of the maze by a multiple of 90 degrees.
The input begins with the integer t, the number of test cases. Then t test cases follow.
Each test case begins with a line containing a single integer n - the number of squares in one row of the maze (1<= n <= 200000). The next n lines contain three integers each, denoting the types of blocks in consecutive columns of the maze. A column description is of the form a b c (0<=a,b,c<=2), where a represents the type of the block in the first row, b - in the second row and c - in the third row.
For each test case output the word yes if it is possible to rotate the squares so as to form a connection between the left and right edge, and the word no in the opposite case.
Sample input: 1 6 1 0 1 1 2 2 2 2 1 2 2 1 2 2 1 1 2 2 Sample output: yes
Indeed, the sample input corresponds to the following maze:
for which there exists a correct solution to the problem:
Getting WA...Even though I've considered every test case I can think of...