Poj 1222 EXTENDED LIGHTS OUT

题目大意:给你一个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();
}
}

AC通道—> http://poj.org/problem?id=1222

上一篇:Core dump去哪里了?


下一篇:POJ 1222 (开关问题+高斯消元法)