codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1360E.md (3078B)


      1 Source: https://codeforces.com/problemset/problem/1360/E
      2 
      3 E. Polygon
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Polygon is not only the best platform for developing problems but also a square matrix with side $n$, initially filled with the character 0.
     22 
     23 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 $2n$ cannons were placed.
     24 
     25  ![](https://espresso.codeforces.com/8dd379eae441ff41f2ccb92e71927fb42dc819ef.png) Initial polygon for $n=4$. 
     26 
     27 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.
     28 
     29 More formally:
     30 
     31 * if a cannon stands in the row $i$, to the left of the first column, and shoots with a 1, then the 1 starts its flight from the cell ($i, 1$) and ends in some cell ($i, j$);
     32 * if a cannon stands in the column $j$, above the first row, and shoots with a 1, then the 1 starts its flight from the cell ($1, j$) and ends in some cell ($i, j$).
     33 
     34 For example, consider the following sequence of shots:
     35 
     36  ![](https://espresso.codeforces.com/38e62f178bc72c48ee77033ca77877d5fe78b343.png)
     37 
     38 1. Shoot the cannon in the row $2$.                         2. Shoot the cannon in the row $2$.                         3. Shoot the cannon in column $3$.
     39 
     40 You have a report from the military training on your desk. This report is a square matrix with side length $n$ 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?
     41 
     42 Each cannon can make an arbitrary number of shots. Before the training, each cell of the polygon contains 0.
     43 
     44 Input
     45 
     46 The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.
     47 
     48 Each test case starts with a line containing an integer $n$ ($1 \le n \le 50$) — the size of the polygon.
     49 
     50 This is followed by $n$ lines of length $n$, consisting of 0 and 1 — the polygon matrix after the training.
     51 
     52 The total area of the matrices in all test cases in one test does not exceed $10^5$.
     53 
     54 Output
     55 
     56 For each test case print:
     57 
     58 * YES if there is a sequence of shots leading to a given matrix;
     59 * NO if such a sequence does not exist.
     60 
     61 The letters in the words YES and NO can be printed in any case.
     62 
     63 Example
     64 
     65 Input
     66 
     67 ```
     68 5
     69 4
     70 0010
     71 0011
     72 0000
     73 0000
     74 2
     75 10
     76 01
     77 2
     78 00
     79 00
     80 4
     81 0101
     82 1111
     83 0101
     84 0111
     85 4
     86 0100
     87 1110
     88 0101
     89 0111
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 YES
     96 NO
     97 YES
     98 YES
     99 NO
    100 ```
    101 
    102 Note
    103 
    104 The first test case was explained in the statement.
    105 
    106 The answer to the second test case is NO, since a 1 in a cell ($1, 1$) flying out of any cannon would continue its flight further.