codeforces-scrape

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

1966B.md (2687B)


      1 Source: https://codeforces.com/problemset/problem/1966/B
      2 
      3 B. Rectangle Filling
      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 There is an $n \times m$ grid of white and black squares. In one operation, you can select any two squares of the same color, and color all squares in the subrectangle between them that color.
     22 
     23 Formally, if you select positions $(x_1, y_1)$ and $(x_2, y_2)$, both of which are currently the same color $c$, set the color of all $(x, y)$ where $\min(x_1, x_2) \le x \le \max(x_1, x_2)$ and $\min(y_1, y_2) \le y \le \max(y_1, y_2)$ to $c$.
     24 
     25 This diagram shows a sequence of two possible operations on a grid:
     26 
     27  ![](https://espresso.codeforces.com/97a106c59497c25abaa5be2c77c8ea88fe571d50.png) 
     28 
     29 Is it possible for all squares in the grid to be the same color, after performing any number of operations (possibly zero)?
     30 
     31 Input
     32 
     33 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     34 
     35 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 500$) — the number of rows and columns in the grid, respectively.
     36 
     37 Each of the next $n$ lines contains $m$ characters 'W' and 'B' — the initial colors of the squares of the grid.
     38 
     39 It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $3\cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print "YES" if it is possible to make all squares in the grid the same color, and "NO" otherwise.
     44 
     45 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 8
     53 
     54 2 1
     55 
     56 W
     57 
     58 B
     59 
     60 6 6
     61 
     62 WWWWBW
     63 
     64 WBWWWW
     65 
     66 BBBWWW
     67 
     68 BWWWBB
     69 
     70 WWBWBB
     71 
     72 BBBWBW
     73 
     74 1 1
     75 
     76 W
     77 
     78 2 2
     79 
     80 BB
     81 
     82 BB
     83 
     84 3 4
     85 
     86 BWBW
     87 
     88 WBWB
     89 
     90 BWBW
     91 
     92 4 2
     93 
     94 BB
     95 
     96 BB
     97 
     98 WW
     99 
    100 WW
    101 
    102 4 4
    103 
    104 WWBW
    105 
    106 BBWB
    107 
    108 WWBB
    109 
    110 BBBB
    111 
    112 1 5
    113 
    114 WBBWB
    115 ```
    116 
    117 Output
    118 
    119 ```
    120 NO
    121 YES
    122 YES
    123 YES
    124 YES
    125 NO
    126 YES
    127 NO
    128 ```
    129 
    130 Note
    131 
    132 In the first example, it is impossible to ever change the color of any square with an operation, so we output NO.
    133 
    134 The second example is the case pictured above. As shown in that diagram, it is possible for all squares to be white after two operations, so we output YES.
    135 
    136 In the third and fourth examples, all squares are already the same color, so we output YES.
    137 
    138 In the fifth example we can do everything in two operations. First, select positions $(2, 1)$ and $(1, 4)$ and color all squares with $1 \le x \le 2$ and $1 \le y \le 4$ to white. Then, select positions $(2, 1)$ and $(3, 4)$ and color all squares with $2 \le x \le 3$ and $1 \le y \le 4$ to white. After these two operations all squares are white.