题意简述
你有两个数字网格 $a$ 和 $b$，每个网格都有 $n$ 行和 $m$ 列。网格中的所有值都是 $0$，$1$ 或 $2$。
你可以对网格 $a$ 进行以下操作任意次：
选择网格中的任意子矩形，其长度和宽度 $\ge 2$。你可以选择整个网格作为子矩形。
子矩形有四个角。选取任意一对对角线上的角，将它们的值加 $1$ 并取模 $3$。
对于未选取的那对角，将它们的值加 $2$ 并取模 $3$。
注意，此操作仅更改所选子矩形的角的值。
是否可以通过上述操作将网格 $a$ 转换为网格 $b$（可以进行零次操作）？
思路分析
首先考虑，对两条对角线的选择是否有些关系？
我们发现，选择任一条对角线 +2 后，如果重复该操作，就变成了选择另一条对角线 +2；
如果再重复该操作，就抵消掉了此次影响。
对于这种问题，我们可以考虑这个操作是否具有可逆性。
因为一旦操作具有可逆性，我们就可以通过一次逆向操作抵消此次操作对于结果的影响。
这个操作显然是有可逆性的。因为我们可以通过在原位置再叠两次该操作使四个角均变为 $3$ 的倍数从而消除影响。
再看是否具有可累加性，即看一个大的矩形操作能否由若干个小矩形操作累加得到。
这点也是显而易见的。在某个矩形操作的末尾一列接上一个相反的矩形操作，即可将原矩形扩大。
换句话说，我们可以通过若干个 $2 \times 2$ 小矩形操作累加出任意一种大矩形操作，且每个位置的矩形累加次数不超过 $2$。
综合上述分析，原题就变成了，在 $a$ 上进行 $(N-1)(M-1)$ 个 $2 \times 2$ 小矩形的 0~2 次叠加操作后，能否使 $a$ 与 $b$ 相等？
现在，我们可以按照顺序依次更新 $a$ 的所有元素。
当一个元素出现在一个 $2 \times 2$ 矩形的左上角时，这是它最后一次被更新。
因此，我们只需要使小矩形左上角的元素在 $a$ 与 $b$ 中相等即可。
但是，对于最右侧和最底侧的元素并没成为过小矩形的左上角，也就是它们的更新仅依赖左侧和上方元素更新时顺带的操作。
检查这些元素是否在 $a$ 与 $b$ 中相等即可。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
using namespace std;
const int maxN = 510;
int A[maxN][maxN];
int B[maxN][maxN];
int C[2][2] = {{1,2},{2,1}};
inline void solve(){
int N,M;
scanf("%d%d",&N,&M);
char s[maxN];
for(int i = 1;i<=N;i++){
scanf("%s",s);
for(int j = 1;j<=M;j++){
A[i][j] = s[j-1] - '0';
}
}
for(int i = 1;i<=N;i++){
scanf("%s",s);
for(int j = 1;j<=M;j++){
B[i][j] = s[j-1] - '0';
}
}
for(int i = 1;i<N;i++){
for(int j = 1;j<M;j++){
if(A[i][j] == B[i][j]) continue;
int a = A[i][j];
int b = B[i][j];
while(A[i][j] != B[i][j]){
for(int t = 0;t<=3;t++){
int x = t >> 1;
int y = t & 1;
A[i+x][j+y] += C[x][y];
A[i+x][j+y] %= 3;
}
}
}
}
for(int i = 1;i<=N;i++){
for(int j = 1;j<=M;j++){
if(A[i][j] != B[i][j]){
printf("NO\n");
return;
}
}
}
printf("YES\n");
}
int main(){
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
|