爱站程序员基地Polygon is not only the best platform for developing problems but also a square matrix with side nn, initially filled with the character 0.
On the polygon, military training was held. The soldiers placed a cannon above each cell in the first row and a cannon to the left of each cell in the first column. Thus, exactly 2n2n cannons were placed.
Initial polygon for n=4n=4.
Cannons shoot character 1. At any moment of time, no more than one cannon is shooting. When a 1 flies out of a cannon, it flies forward (in the direction of the shot) until it collides with a polygon border or another 1. After that, it takes the cell in which it was before the collision and remains there. Take a look at the examples for better understanding.
More formally:
- if a cannon stands in the row ii, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell (i,1i,1) and ends in some cell (i,ji,j);
- if a cannon stands in the column jj, above the first row, and shoots with a 1, then the 1 starts its flight from the cell (1,j1,j) and ends in some cell (i,ji,j).
For example, consider the following sequence of shots:
1. Shoot the cannon in the row 22. 2. Shoot the cannon in the row 22. 3. Shoot the cannon in column 33.
You have a report from the military training on your desk. This report is a square matrix with side length nn consisting of 0 and 1. You wonder if the training actually happened. In other words, is there a sequence of shots such that, after the training, you get the given matrix?
Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.
Input
The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases. Then tt test cases follow.
Each test case starts with a line containing an integer nn (1≤n≤501≤n≤50) — the size of the polygon.
This is followed by nn lines of length nn, consisting of 0 and 1 — the polygon matrix after the training.
The total area of the matrices in all test cases in one test does not exceed 105105.
Output
For each test case print:
- YES if there is a sequence of shots leading to a given matrix;
- NO if such a sequence does not exist.
The letters in the words YES and NO can be printed in any case.
Example
Input
[code]54001000110000000021001200004010111110101011140100111001010111
Output
[code]YESNOYESYESNO
Note
The first test case was explained in the statement.
The answer to the second test case is NO, since a 1 in a cell (1,11,1) flying out of any cannon would continue its flight further.
题意：多组输入，每组给出一个大小为n*n的棋盘。游戏设定为，棋盘的初始全为0，发射纵向或者横向的炮弹可以使尽头的一个格子变为“1”.试判断给出发射过炮弹后的棋盘是否严格遵循了游戏规则。是则输出YES，否则输出NO。
题解：哇再次暴风哭泣，是我把它想复杂了，只需要暴力遍历，在a[i][j]出现“1”的时候，只要a[i+1][j]或者a[i][j+1]其中一个也是“1”即遵循规则，遍历完整个棋盘，判断其是否严格遵循。
[code]#include<iostream>#include<algorithm>using namespace std;int t, n;char a[51][51];int main(){scanf(\"%d\", &t);while(t--){scanf(\"%d\", &n);for(int i=0; i<n; i++)scanf(\"%s\", a[i]);int flag = 1;for(int i=0; i<n-1; i++){if(!flag) break;for(int j=0; j<n-1; j++)if(a[i][j] == \'1\')if(a[i][j+1]==\'0\' && a[i+1][j]==\'0\'){ flag = 0;break;}}if(flag) printf(\"YES\\n\");else printf(\"NO\\n\");}return 0;}
