1983B.md (3366B)
1 Source: https://codeforces.com/problemset/problem/1983/B 2 3 B. Corner Twist 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 You are given two grids of numbers $a$ and $b$, with $n$ rows and $m$ columns. All the values in the grid are $0$, $1$ or $2$. 22 23 You can perform the following operation on $a$ any number of times: 24 25 * Pick any subrectangle in the grid with length and width $\ge 2$. You are allowed to choose the entire grid as a subrectangle. 26 * The subrectangle has four corners. Take any pair of diagonally opposite corners of the chosen subrectangle and add $1$ to their values modulo $3$. 27 * For the pair of corners not picked, add $2$ to their values modulo $3$. 28 29 Note that the operation only changes the values of the corners of the picked subrectangle. 30 31 Is it possible to convert the grid $a$ into grid $b$ by applying the above operation any number of times (possibly zero)? 32 33 Input 34 35 The first line contains an integer $t$, the number of testcases ($1 \le t \le 250$). 36 37 For each testcase: 38 39 The first line contains two integers $n$ and $m$, the number of rows and columns in the grid ($2 \le n,m \le 500$). 40 41 Each of the next n lines contain m characters — the $j$-th character of the $i$-th line represents $a_{i,j}$. 42 43 Each of the next n lines contain m characters — the $j$-th character of the $i$-th line represents $b_{i,j}$ ($0 \le a_{i,j}, b_{i,j} \le 2$). 44 45 It is guaranteed that the sum of $n$ over all test cases and the sum of $m$ over all test cases do not exceed $500$. 46 47 Output 48 49 For each test case print "YES" (without quotes) if it is possible to convert grid $a$ into grid $b$ and "NO" (without quotes) otherwise. 50 51 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. 52 53 Example 54 55 Input 56 57 ``` 58 7 59 60 3 3 61 62 000 63 64 000 65 66 000 67 68 111 69 70 111 71 72 111 73 74 4 4 75 76 0000 77 78 0000 79 80 0000 81 82 0000 83 84 2100 85 86 1200 87 88 0012 89 90 0021 91 92 4 4 93 94 1020 95 96 1200 97 98 1210 99 100 0000 101 102 0000 103 104 1200 105 106 2200 107 108 0000 109 110 3 3 111 112 012 113 114 012 115 116 012 117 118 010 119 120 111 121 122 011 123 124 8 8 125 126 00000000 127 128 00000000 129 130 00000000 131 132 00000000 133 134 00000000 135 136 00000000 137 138 00000000 139 140 10000000 141 142 00000000 143 144 01200000 145 146 02010000 147 148 00102000 149 150 00020100 151 152 00001020 153 154 00000210 155 156 10000000 157 158 2 7 159 160 0000000 161 162 0000000 163 164 2220111 165 166 0111222 167 168 2 7 169 170 0000000 171 172 0100010 173 174 2220111 175 176 1210202 177 ``` 178 179 Output 180 181 ``` 182 YES 183 YES 184 YES 185 NO 186 YES 187 NO 188 YES 189 ``` 190 191 Note 192 193 In the first testcase, grid $a$ can be converted into $b$ in the following manner: 194 195 $\begin{matrix}\fbox{0} & 0 & \fbox{0}\\ 0 & 0 & 0\\ \fbox{0} & 0 & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ 0 & \fbox{0} & \fbox{0}\\ 2 & \fbox{0} & \fbox{1}\end{matrix} \Rightarrow \begin{matrix}1 & 0 & 2\\ \fbox{0} & \fbox{1} & 2\\ \fbox{2} & \fbox{2} & 2\end{matrix} \Rightarrow \begin{matrix}1 & \fbox{0} & \fbox{2}\\ 1 & 0 & 2\\ 1 & \fbox{0} & \fbox{2}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & \fbox{0} & \fbox{2}\\ 1 & \fbox{2} & \fbox{0}\end{matrix} \Rightarrow \begin{matrix}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{matrix}$ 196 197 Here, in each operation, the top-right and bottom-left corners highlighted by a box are incremented by $2$ modulo $3$, while the top-left and bottom-right corners are incremented by $1$ modulo $3$. 198 199 In the fourth testcase, it can be proven that it is not possible to convert grid $a$ into grid $b$ using the above-mentioned operations any number of times.