1647B.md (2566B)
1 Source: https://codeforces.com/problemset/problem/1647/B 2 3 B. Madoka and the Elegant Gift 4 5 time limit per test 6 7 1 second 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 Madoka's father just reached $1$ million subscribers on Mathub! So the website decided to send him a personalized award — The Mathhub's Bit Button! 22 23 The Bit Button is a rectangular table with $n$ rows and $m$ columns with $0$ or $1$ in each cell. After exploring the table Madoka found out that: 24 25 * A subrectangle $A$ is contained in a subrectangle $B$ if there's no cell contained in $A$ but not contained in $B$. 26 * Two subrectangles intersect if there is a cell contained in both of them. 27 * A subrectangle is called black if there's no cell with value $0$ inside it. 28 * A subrectangle is called nice if it's black and it's not contained in another black subrectangle. 29 * The table is called elegant if there are no two nice intersecting subrectangles. 30 31 For example, in the first illustration the red subrectangle is nice, but in the second one it's not, because it's contained in the purple subrectangle. 32 33  34 35 Help Madoka to determine whether the table is elegant. 36 37 Input 38 39 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 200$) — the number of test cases. Description of the test cases follows. 40 41 The first line of each test case contains two positive integers $n, m$ ($1 \le n, m \le 100$). 42 43 The next $n$ lines contain strings of length $m$ consisting of zeros and ones — the description of the table. 44 45 It is guaranteed that the sum of the values of $n$ and the sum of the values of $m$ for all test cases do not exceed $777$. 46 47 Output 48 49 For each test case print "YES" if its table is elegant or print "NO" otherwise. 50 51 You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer). 52 53 Example 54 55 Input 56 57 ``` 58 5 59 60 3 3 61 62 100 63 64 011 65 66 011 67 68 3 3 69 70 110 71 72 111 73 74 110 75 76 1 5 77 78 01111 79 80 4 5 81 82 11111 83 84 01010 85 86 01000 87 88 01000 89 90 3 2 91 92 11 93 94 00 95 96 11 97 ``` 98 99 Output 100 101 ``` 102 YES 103 NO 104 YES 105 NO 106 YES 107 ``` 108 109 Note 110 111 In the second test case the table is not elegant, because the red and the purple subrectangles are nice and intersect. 112 113  114 115 In the fourth test case the table is not elegant, because the red and the purple subrectangles are nice and intersect. 116 117 