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+1;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+1;k++)
        w[j][k]=w[j][k]^w[i][k];
}

void print(){    
    for(int i=1;i<=n*m;i++){
        for(int j=1;j<=m*n+1;j++)
            printf("%d ",w[i][j]);
        printf("\n");
    }    
    printf("\n\n");
}

void gauss(){                        //高斯消元 解 异或方程 
    //print();
    
    for(int i=1;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+1;j<=m*n;j++)
            if(w[j][i])
                Xor(i,j);
    }
    
    //print();
    
    for(int i=m*n;i>=1;i--){
        x[i]=w[i][m*n+1];
        if(!x[i])    continue;
        for(int j=i-1;j>=1;j--)
            if(w[j][i])
                w[j][m*n+1]^=x[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",x[(i-1)*m+j]);
        printf("\n");
    }
}

void prework(){
    n=5,m=6;
    memset(w,0,sizeof(w));
    for(int i=1;i<=n;i++)    
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]),w[(i-1)*m+j][m*n+1]=a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            w[(i-1)*m+j][(i-1)*m+j]=1;                //自己和上下左右是对自己有影响的点 
            if(j!=1) w[(i-1)*m+j][(i-1)*m+j-1]=1;
            if(j!=m) w[(i-1)*m+j][(i-1)*m+j+1]=1;
            if(i!=n) w[(i-1)*m+j][i*m+j]=1;
            if(i!=1) w[(i-1)*m+j][(i-2)*m+j]=1;
        }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
#endif
    int T,cnt=0;
    scanf("%d",&T);
    while(T--){
        prework();
        printf("PUZZLE #%d\n",++cnt);
        gauss();
    }
}

View Code

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

Poj 1222 EXTENDED LIGHTS OUT

推荐阅读