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  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.