← 返回题目列表

Codeforces · 1119/C

C. 拉美西斯和角反转

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

Ramesses来到大学进行算法实践,他的教授是一位相当知名的程序员,给了他以下任务。

给你两个矩阵 $$$A$$$ 和 $$$B$$$,大小为 $$$n \times m$$$,每个矩阵仅由 $$$0$$$ 和 $$$1$$$ 组成。您可以对矩阵$$$A$$$应用以下操作任意次数:取矩阵$$$A$$$中至少有两行和两列的任何子矩阵,并反转其角上的值(即包含$$$0$$$的子矩阵的所有角将被$$$1$$$替换,并且包含$$$1$$$的子矩阵的所有角将被替换为$$$1$$$。 $$$0$$$)。你必须回答是否可以从矩阵$$$A$$$得到矩阵$$$B$$$。

操作示例。所选子矩阵以蓝色和黄色显示,其角以黄色显示。

拉美西斯不想自己执行这些操作,所以他要求你回答这个问题。

矩阵 $$$M$$$ 的子矩阵是由来自矩阵 $$$M$$$ 索引 $$$x_1, x_1+1, \ldots, x_2$$$ 的行之一和矩阵 $$$M$$$ 索引 $$$y_1, y_1+1, \ldots, y_2$$$ 的列之一组成的矩阵,其中 $$$x_1, x_2, y_1, y_2$$$ 是子矩阵的边缘行和列。换句话说,子矩阵是源矩阵的一组元素,它们形成一个实心矩形(即没有孔),其边与原始矩阵的边平行。子矩阵的角点是单元格 $$$(x_1, y_1)$$$、$$$(x_1, y_2)$$$、$$$(x_2, y_1)$$$、$$$(x_2, y_2)$$$,其中单元格 $$$(i,j)$$$ 表示第 $$$i$$$ 行与第 $$$j$$$ 列。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 500$$$) - 矩阵 $$$A$$$ 和 $$$B$$$ 中的行数和列数。

接下来的 $$$n$$$ 行均包含 $$$m$$$ 整数:第 $$$i$$$ 行中的第 $$$j$$$ 整数是矩阵 $$$A$$$ 的第 $$$i$$$ 行的第 $$$j$$$ 元素 ($$$0 \leq A_{ij} \leq 1$$$)。

接下来的 $$$n$$$ 行均包含 $$$m$$$ 整数:第 $$$i$$$ 行中的第 $$$j$$$ 整数是矩阵 $$$B$$$ 的第 $$$i$$$ 行的第 $$$j$$$ 元素 ($$$0 \leq B_{ij} \leq 1$$$)。

输出

如果可以使用上述操作将矩阵 $$$A$$$ 转换为矩阵 $$$B$$$,则打印“Yes”(不带引号);如果不可能,则打印“No”(不带引号)。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

3 3
0 1 0
0 1 0
1 0 0
1 0 0
1 0 0
1 0 0

输出 #1

Yes

输入 #2

6 7
0 0 1 1 0 0 1
0 1 0 0 1 0 1
0 0 0 1 0 0 1
1 0 1 0 1 0 0
0 1 0 0 1 0 1
0 1 0 1 0 0 1
1 1 0 1 0 1 1
0 1 1 0 1 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 1 1 1 1 0 1

输出 #2

Yes

输入 #3

3 4
0 1 0 1
1 0 1 0
0 1 0 1
1 1 1 1
1 1 1 1
1 1 1 1

输出 #3

No

注意

示例解释如下。

示例 1。

示例 2。

示例 3。