理解一下题意，题目给了n*m的灯，你可以关闭某一盏灯，同时，和这盏灯相距曼哈顿距离为d的灯也会被反转状态(关的变成开的，开的变成关的)
我们说点(x1,y1)和点(x2,y2)的曼哈顿距离为d，如果
|x1-x2|+|y1-y2|==d
现在给出这n*m灯的状态 问：是否可以通过一系列开关灯的操作 使得所有的灯都变成关闭状态(0)
1代表开 0代表关
先来分析一下 如果我们从头到尾扫一遍这些灯 把开的灯关掉 这样循环 能不能到达”全部都是关的”这个状态？
就拿sample input来说 其中第二组数据
2 2 1
1 1
1 1
我们这样操作：
1 1 -> 0 0 -> 0 1 -> 1 0 -> 0 1 -> 1 0 -> 0 1 -> 1 0
1 1 -> 0 1 -> 1 0 -> 1 1 -> 0 1 -> 0 0 -> 1 0 -> 1 1
看出来 第四组和第八组是相同的 所以这样做会进入一个循环 所以是不可行的
那有没有好一点的方案呢？
显然是有的
我们设我们需要对第i行j列的灯操作 a((i-1)*m+j) 次
（这里的(i-1)*m+j是下标）
那么我们可以知道最终所有的灯被开关的次数
举个栗子
数据：
2 2 1
1 1
1 1
所有的灯被操作的次数为：
a1+a2+a3 a1+a2+a4
a1+a3+a4 a2+a3+a4
然后我们把问题做个等价转换：
如果我可以在初始状态通过一系列操作到达全灭
那么我也可以在全灭状态通过一系列操作到达初始状态
反之
（怎么操作到全灭的，逆着操作回去就行了）
期间再做个优化 开关灯的操作可以用 模2加 运算来表示
即 异或 运算
好了 现在我们列出方程组
a1+a2+a3=1
a1+a2+a4=1
a1+a3+a4=1
a2+a3+a4=1
求问 这个方程有木有解？
如果有解 输出1 反之 输出0
类似的可以推到任意个灯的情形
此类问题 用到的是高斯消元算法
我们对方程组的增广矩阵进行行变换操作
不同的是 我们不是拿某一行的元素去加上（或者减去）某一行
而是拿某一行的元素去异或某一行
其他操作类似数学上的高斯消元法
以下是代码：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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92//C++ code
using namespace std;
int n,m,d;
bool pp[30][30];
bool a[700][700];
bool c[700];
int equ,var;
inline int index(int x,int y){
return (x-1)*m+y;
}
inline void _swap(int row1,int row2){
//swap row1 and row2
if(row1==row2) return;
for(int i=1;i<=var;i++){
bool tmp;
tmp=a[row1][i];
a[row1][i]=a[row2][i];
a[row2][i]=tmp;
}
bool t=c[row1];
c[row1]=c[row2];
c[row2]=t;
return;
}
inline bool Guass(){
for(int i=1;i<=var;i++){
int one=-1;
for(int j=i;j<=equ;j++) if(a[j][i]) {one=j;break;}
if(one==-1) continue;
_swap(one,i);
for(int j=1;j<=equ;j++) {
if(j==i||!a[j][i]) continue;
for(int k=i;k<=var;k++) a[j][k]^=a[i][k];
c[j]^=c[i];
}
}
for(int i=1;i<=equ;i++){
if(!a[i][i]&&c[i]) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("input.in","r",stdin);
// int begin_time=clock();
while(cin>>m>>n>>d){
if(n==0&&m==0&&d==0) break;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>pp[i][j];
}
}
var=n*m;
equ=n*m;
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int row=index(i,j);
a[row][row]=1;
if(i-d>=1) a[row][index(i-d,j)]=1;
if(i+d<=n) a[row][index(i+d,j)]=1;
if(j-d>=1) a[row][index(i,j-d)]=1;
if(j+d<=m) a[row][index(i,j+d)]=1;
for(int k=1;k<d;k++) {
int nx,ny;
nx=i-k;ny=j+(d-k);
if(nx>=1&&ny>=1&&nx<=n&&ny<=m) a[row][index(nx,ny)]=1;
nx=i+k;ny=j+(d-k);
if(nx>=1&&ny>=1&&nx<=n&&ny<=m) a[row][index(nx,ny)]=1;
nx=i-k;ny=j-(d-k);
if(nx>=1&&ny>=1&&nx<=n&&ny<=m) a[row][index(nx,ny)]=1;
nx=i+k;ny=j-(d-k);
if(nx>=1&&ny>=1&&nx<=n&&ny<=m) a[row][index(nx,ny)]=1;
}//make a
c[row]=pp[i][j];//make c
}
}
if(!Guass()) cout<<0<<endl;
else cout<<1<<endl;
}
// cout<<"time use: "<<clock()-begin_time<<" ms"<<endl;
return 0;
}