Recursive Ants

In a 2^n*2^n chess board, some grids is marked visitable, and others are not. Mr. Ant is planning to visit all the visitable grids on the board, and each grid can be visited only once. Mr. Ant start from the left-top side of the board, and he should finish his journey at any grid on the edge of the board. Of course we assume that the start point of Mr. Ant is always visitable.
In every step, Mr. Ant can move from one grid to the adjacent grid (that is to say he can move up, down, left, right in four directions).
Mr. Ant’s path is defined recursively. That is to say, if Mr. Ant wants to visit a 2^k*2^k chess board, then we divided the board into four pieces, and each one has a size of 2^(k-1)*2^(k-1), in every part, Mr. Ant should visit all the grids in the four parts and then move onto another. Of course, we should divided this 2^(k-1)*2^(k-1) board into four smaller pieces and Mr. Ant’s path should be defined in these new four parts.

The input-file consists of several test cases. There is a number n (1<= n <=7) in the beginning of each test case indicating that the width of the chess board: 2^n*2^n. Each of the next 2n lines contains a string. Character ‘1’ means visitable and ‘0’ means not. Input-file is end with an end-of-file character.

For every case, you only need to output one line. Output “YES” if Mr. Ant can finish his journey as described above, else output “NO”.

1
11
10
2
1100
0110
0111
0111
3
11001100
01111100
01111111
01111111
11111111
11111111
00001111
00001111

NO
NO
YES

2009 Multi-University Training Contest 17 - Host by NUDT