CF1119C Ramesses and Corner Inversion
题目描述
Ramesses 来到大学进行算法练习,他的教授(也是一位著名的程序员)给了他如下任务。
给定两个 $n \times m$ 的矩阵 $A$ 和 $B$,每个矩阵的元素均为 $0$ 或 $1$。你可以对矩阵 $A$ 任意次地进行如下操作:任选一个至少包含两行两列的子矩阵,将其四个角上的元素取反(即,角上的 $0$ 变为 $1$,$1$ 变为 $0$)。你需要判断,是否可以通过若干次上述操作,将矩阵 $A$ 变为矩阵 $B$。

操作示例。选中的子矩阵用蓝色和黄色表示,角上的元素为黄色。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"(不含引号)。输出时字母大小写均可。
说明/提示
下面对样例进行解释。

样例 1。

样例 2。

样例 3。
由 ChatGPT 4.1 翻译