题目大意:给你一个5*6的格子,每个格子中有灯(亮着1,暗着0),每次你可以把一个暗的点亮(或者亮的熄灭)然后它上下左右的灯也会跟着变化。最后让你把所有的灯熄灭,问你应该改变哪些灯。
首先我们可以发现,如果我们对一个灯操作2次,等于啥也没干,所以呢,每个点只有可能有两种状态,操作或不操作。
但是每个点的状态不只和自己有关,还与它周围的四个点有关,是吧?
所以相当于对于每个点解一个方程:
之前的状态 XOR 自己变没变 XOR 周围的四个点变没变 = 目标状态 (暗着)
稍稍变动一下,两边同时XOR之前的状态。
自己变没变 XOR 周围的四个点变没变 = 之前的状态
然后把所有点的异或方程合在一起,就得到了一个异或方程组。
解开这个方程组就大事告成了!
为了咱们解方程比较简单,我们可以在这个点的异或方程中,把影响到这个点的点的系数a记为1,不影响的记为0,将每个点是否操作作为所求的变量x1..n(n为点数),最终状态b作为方程的右边。
a1*x1 xor a2*x2 xor a3*x3 xor ... xor an*xn = b
其中a,x,b的取值都是1或0(ai的值表示是否对这个点有影响,b的值表示最后是否亮着,xi的值表示是否对点i进行操作),考虑完单个点的情况,再将所有点的方程加入:
a11*x1 xor a12*x2 xor a13*x3 xor ... xor a1n*xn = b1
a21*x1 xor a22*x2 xor a23*x3 xor ... xor a2n*xn = b2
... ... ... ...
an1*x1 xor an2*x2 xor an3*x3 xor ... xor ann*xn = bn
从而得到一个n*n的矩阵,再加上一列最终状态构成的列向量。
a11 a12 a13 ... a1n b1
a21 a22 a23 ... a2n b2
... ... ... ...
an1 an2 an3 ... ann bn
然后就是高斯消元时间啦!!——>见【高斯消元】
/*
Poj 1222
Author: Robert_Yuan
Memory: 364K
Time: 0MS
*/
#include<cstdio>
#include<cstring> using namespace std; #define maxn 32 int n,m;
int x[maxn];
int a[maxn][maxn];
int w[maxn][maxn]; //w[i][j] 表示 i,j是否能互相影响 void swap(int i,int j){
int t;
for(int k=i;k<=m*n+;k++)
t=w[i][k],w[i][k]=w[j][k],w[j][k]=t;
} void Xor(int i,int j){
for(int k=i;k<=m*n+;k++)
w[j][k]=w[j][k]^w[i][k];
} void print(){
for(int i=;i<=n*m;i++){
for(int j=;j<=m*n+;j++)
printf("%d ",w[i][j]);
printf("\n");
}
printf("\n\n");
} void gauss(){ //高斯消元 解 异或方程
//print(); for(int i=;i<=m*n;i++){
bool find=false;
for(int j=i;j<=m*n;j++)
if(w[j][i]){
swap(i,j);find=true;break;
}
if(!find) continue;
for(int j=i+;j<=m*n;j++)
if(w[j][i])
Xor(i,j);
} //print(); for(int i=m*n;i>=;i--){
x[i]=w[i][m*n+];
if(!x[i]) continue;
for(int j=i-;j>=;j--)
if(w[j][i])
w[j][m*n+]^=x[i];
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
printf("%d ",x[(i-)*m+j]);
printf("\n");
}
} void prework(){
n=,m=;
memset(w,,sizeof(w));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]),w[(i-)*m+j][m*n+]=a[i][j];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
w[(i-)*m+j][(i-)*m+j]=; //自己和上下左右是对自己有影响的点
if(j!=) w[(i-)*m+j][(i-)*m+j-]=;
if(j!=m) w[(i-)*m+j][(i-)*m+j+]=;
if(i!=n) w[(i-)*m+j][i*m+j]=;
if(i!=) w[(i-)*m+j][(i-)*m+j]=;
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
freopen("x.out","w",stdout);
#endif
int T,cnt=;
scanf("%d",&T);
while(T--){
prework();
printf("PUZZLE #%d\n",++cnt);
gauss();
}
}