CF1119C Ramesses and Corner Inversion

题目描述

Ramesses 来到大学进行算法练习,他的教授(也是一位著名的程序员)给了他如下任务。 给定两个 $n \times m$ 的矩阵 $A$ 和 $B$,每个矩阵的元素均为 $0$ 或 $1$。你可以对矩阵 $A$ 任意次地进行如下操作:任选一个至少包含两行两列的子矩阵,将其四个角上的元素取反(即,角上的 $0$ 变为 $1$,$1$ 变为 $0$)。你需要判断,是否可以通过若干次上述操作,将矩阵 $A$ 变为矩阵 $B$。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1119C/07e01026afbc60b96857b7392bf73ad937a6aa47.png) 操作示例。选中的子矩阵用蓝色和黄色表示,角上的元素为黄色。Ramesses 不想亲自操作,所以他请你来回答这个问题。 矩阵 $M$ 的一个子矩阵,是指由 $M$ 的第 $x_1, x_1+1, \ldots, x_2$ 行和第 $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"(不含引号)。输出时字母大小写均可。

说明/提示

下面对样例进行解释。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1119C/e8b2b05f1d91acad1dd27cd7e9d641b53a14a9dc.png) 样例 1。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1119C/a67a1a76d04df99ed90143acfb49e6763fb445d5.png) 样例 2。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1119C/8179b88f909d57a1d5601735cc5b6ce16cfe2cb8.png) 样例 3。 由 ChatGPT 4.1 翻译