A4835 | 《终末网格:同行的契约》
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
给你两个由数字 $a$ 和 $b$ 组成的网格，网格中有 $n$ 行和 $m$ 列。网格中的所有数值都是 $0$ 、 $1$ 或 $2$ 。
您可以多次对 $a$ 执行以下操作：
- 选取网格中任意一个长宽为 $\ge 2$ 的子矩形。您可以选择整个网格作为子矩形。
- 子矩形有四个角。取所选子矩形中任意一对斜对角，并将它们的值加上 $1$后 mod $3$ 。
- 对于未选中的一对角，在它们的值上加上 $2$后 mod $3$ 。
需要注意的是，此操作只改变被选中的子矩形的角的值。
是否可以通过任意次数（可能为零）的上述操作将网格 $a$ 转换为网格 $b$ ？
您可以多次对 $a$ 执行以下操作：
- 选取网格中任意一个长宽为 $\ge 2$ 的子矩形。您可以选择整个网格作为子矩形。
- 子矩形有四个角。取所选子矩形中任意一对斜对角，并将它们的值加上 $1$后 mod $3$ 。
- 对于未选中的一对角，在它们的值上加上 $2$后 mod $3$ 。
需要注意的是，此操作只改变被选中的子矩形的角的值。
是否可以通过任意次数（可能为零）的上述操作将网格 $a$ 转换为网格 $b$ ？
输入格式
第一行包含一个整数 $t$ ，即测试用例数。
对于每个测试用例
第一行包含两个整数 $n$ 和 $m$ ，即网格的行数和列数。
接下来的 n 行中，每一行都包含 m 个字符-- $i$ 行中的 $j$ th 字符代表 $a_{i,j}$ 。
接下来的 n 行中的每一行都包含 m 个字符 - $i$ th 行的 $j$ th 字符代表 $b_{i,j}$ 。
( $0 \le a_{i,j}, b_{i,j} \le 2$ )。
数据范围：（$10 \le t \le 200$ ),( $2 \le n,m \le 100$ )
保证所有测试用例的 $n$* $m$ 不超过 $500$ 。
对于每个测试用例
第一行包含两个整数 $n$ 和 $m$ ，即网格的行数和列数。
接下来的 n 行中，每一行都包含 m 个字符-- $i$ 行中的 $j$ th 字符代表 $a_{i,j}$ 。
接下来的 n 行中的每一行都包含 m 个字符 - $i$ th 行的 $j$ th 字符代表 $b_{i,j}$ 。
( $0 \le a_{i,j}, b_{i,j} \le 2$ )。
数据范围：（$10 \le t \le 200$ ),( $2 \le n,m \le 100$ )
保证所有测试用例的 $n$* $m$ 不超过 $500$ 。
输出格式
对于每个测试用例，如果可以将网格 $a$ 转换为网格 $b$ ，则打印 "YES"（不带引号），否则打印 "NO"（不带引号）。
输入输出样例
输入 #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{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}$
这里，在每次操作中，方框突出显示的右上角和左下角都会以 $2$ mod $3$ 的方式递增，而左上角和右下角则以 $1$ mod $3$ 的方式递增。
在第四个测试案例中，可以证明使用上述操作不可能多次将网格 $a$ 转换为网格 $b$ 。
在第一个测试案例中，网格 $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{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}$
这里，在每次操作中，方框突出显示的右上角和左下角都会以 $2$ mod $3$ 的方式递增，而左上角和右下角则以 $1$ mod $3$ 的方式递增。
在第四个测试案例中，可以证明使用上述操作不可能多次将网格 $a$ 转换为网格 $b$ 。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？