← 返回题目列表

Codeforces · 1983/B

B. 角扭曲

中文机器翻译题面 查看原题

给你两个数字 $$$a$$$ 和 $$$b$$$ 网格,其中 $$$n$$$ 行和 $$$m$$$ 列。网格中的所有值均为 $$$0$$$、$$$1$$$ 或 $$$2$$$。

您可以对 $$$a$$$ 执行以下操作任意次:

- 在网格中选取任意长度和宽度为 $$$\ge 2$$$ 的子矩形。您可以选择整个网格作为子矩形。
- 子矩形有四个角。取所选子矩形的任意一对对角,并将 $$$1$$$ 加上它们的值模 $$$3$$$。
- 对于未选取的一对角,将 $$$2$$$ 添加到其值模 $$$3$$$ 中。

请注意,该操作仅更改选取的子矩形的角点的值。

是否可以通过应用上述操作任意次数(可能为零)将网格$$$a$$$转换为网格$$$b$$$?

输入

第一行包含一个整数 $$$t$$$,即测试用例的数量 ($$$1 \le t \le 250$$$)。

对于每个测试用例:

第一行包含两个整数 $$$n$$$ 和 $$$m$$$,即网格中的行数和列数 ($$$2 \le n,m \le 500$$$)。

接下来的 n 行中的每一行都包含 m 个字符 — 第 $$$i$$$ 行的第 $$$j$$$ 字符代表 $$$a_{i,j}$$$。

接下来的 n 行中的每一行都包含 m 个字符 — 第 $$$i$$$ 行的第 $$$j$$$ 个字符表示 $$$b_{i,j}$$$ ($$$0 \le a_{i,j}, b_{i,j} \le 2$$$)。

保证所有测试用例的$$$n$$$总和以及所有测试用例的$$$m$$$总和不超过$$$500$$$。

输出

对于每个测试用例,如果可以将网格 $$$a$$$ 转换为网格 $$$b$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

7
3 3
000
000
000
111
111
111
4 4
0000
0000
0000
0000
2100
1200
0012
0021
4 4
1020
1200
1210
0000
0000
1200
2200
0000
3 3
012
012
012
010
111
011
8 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
10000000
00000000
01200000
02010000
00102000
00020100
00001020
00000210
10000000
2 7
0000000
0000000
2220111
0111222
2 7
0000000
0100010
2220111
1210202

输出 #1

YES
YES
YES
NO
YES
NO
YES

注意

在第一个测试用例中,网格 $$$a$$$ 可以通过以下方式转换为 $$$b$$$:

$$$\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{矩阵} \Rightarrow \begin{矩阵}1 & 1 & 1\\ 1 & \fbox{0} & \fbox{2}\\ 1 & \fbox{2} & \fbox{0}\end{矩阵} \Rightarrow \begin{矩阵}1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1\end{矩阵}$$$

这里,在每次操作中,框突出显示的右上角和左下角都会以 $$$2$$$ 模 $$$3$$$ 递增,而左上角和右下角会以 $$$1$$$ 模 $$$3$$$ 递增。

在第四个测试用例中,可以证明使用上述操作任意次数都不可能将网格 $$$a$$$ 转换为网格 $$$b$$$。