题目大意
有这样一种魔板：它是一个长方形的面板，被划分成$n$行$m$列的$n*m$个方格。每个方格内有一个小灯泡，灯泡的状态有两种(亮或暗)。我们可以通过若干操作使魔板从一个状态改变为另一个状态。操作的方式有两种：
(1)任选一行，改变该行中所有灯泡的状态，即亮的变暗、暗的变亮；
(2)任选两列，交换其位置。
当然并不是任意的两种状态都可以通过若干操作来实现互相转化的。
你的任务就是根据给定两个魔板状态，判断两个状态能否互相转化。
题目分析
第一眼可以上一个简单的Bfs，然后发现状态量有点大。
因为变换是在行中进行的，因此无论如何变换，一行中$0/1$的数目只会发生交换而不会变化。
不妨枚举结束状态$ed$的第一列是由起始状态$st$哪一列交换而来，那么任意行改变$0/1$的方案就唯一确定了。
接下来再任意交换检查其能否到达$ed$状态即可。
代码
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,m;
struct State {
bool a[105][105];
bool* operator [] (const int& x) {
return a[x];
}
void row(int x) {
for(int i=1; i<=m; i++)a[x][i]=!a[x][i];
}
void line(int x,int y) {
for(int i=1; i<=n; i++)swap(a[i][x],a[i][y]);
}
} st,ed;
bool Same(State a,int x,State b,int y) {
for(int i=1; i<=n; i++)
if(a[i][x]!=b[i][y])return false;
return true;
}
int t;
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
st[i][j]=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
ed[i][j]=Get_Int();
bool bj=0;
for(int k=1; k<=m; k++) {
State tmp=st;
tmp.line(1,k);
for(int i=1; i<=n; i++)
if(tmp[i][1]!=ed[i][1])tmp.row(i);
for(int i=1; i<=m; i++) {
bj=0;
for(int j=i; j<=m; j++)
if(Same(tmp,j,ed,i)) {
tmp.line(i,j);
bj=1;
break;
}
if(!bj)break;
}
if(bj)break;
}
if(bj)puts("YES");
else puts("NO");
}
return 0;
}
|
