codeforces-scrape

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

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  ![](https://espresso.codeforces.com/809fd7506f4fcee686dddb27cfbeb4b54f6169cf.png) 
     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  ![](https://espresso.codeforces.com/3d20098d1d8931e5beaf06484ff140482a74c4f1.png) 
    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  ![](https://espresso.codeforces.com/038ed90e0e2caedf78852abe2870aa4e772ebd94.png)