poj 1222 EXTENDED LIGHTS OUT

EXTENDED LIGHTS OUT

題意:給一個5*6的01矩陣，對一個位置操作(0->1開燈或者1->0關燈)會影響到（包括自己）周邊燈狀態反轉。問最後要使得所有的燈關掉的操作矩陣(1表示該位置的燈操作了)

提示:01矩陣，題目給了說是操作兩次就相當於沒操作，但是還有隱含的意思就是這就是一個異或操作(就是和mod2);對於01矩陣加上操作矩陣得到0矩陣，可知所作用的矩陣和原矩陣相同；(操作矩陣:如對（0,0）操作就相當於加上只有左上角有3個1的矩陣，但是把這個矩陣轉化為了一個維度為30的向量形式，有30棧燈所以下麵是一個30*30的矩陣)這是高斯消元列方程的基礎；

高斯消元法:最重要的是要想到構造出一個30*30的作用矩陣，第i列數字中(列號0~29表示燈的標號)1表示第i盞燈操作會影響到1所對應的行號的燈，存儲在增廣矩陣a[][]中;

所謂增廣矩陣就是抽象出只含方程組的繫數和結果的矩陣（簡化書寫）。這樣第i盞燈最終的狀態a[i][30] = Σ(a[i][j]*x[j])(0 <= j < 30)。這就是為什麼在最後化成了上三角之後怎麼是對行向量操作的原因；(a[i][j] && x[j]表示第j盞燈操作會影響到第i盞燈，並且第j盞燈是開的。還有一個前提就是a[i][i] = 1,所以x[i] = a[i][var])

註:在高斯消元列方程轉移到矩陣時，最好直接看每一個繫數與變數之間的對應關係，而不是用行向量與列向量來看。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
int dir[2][4] = {{0,1,0,-1},{1,0,-1,0}};
int a[35][35];
int equ,var;
int x[35];
int Guass()
{
    int i,j,k,free_var = 0;
    rep0(i,0,equ){
        int mx = i;
        rep0(j,i+1,equ)
            if(abs(a[j][i]) > abs(a[mx][i]))  mx = j;
        if(a[mx][i] == 0){
            free_var++;
            continue;
        }
        if(mx != i)
            rep1(k,i,var)
                swap(a[i][k],a[mx][k]);
        rep0(j,i+1,equ){
            if(a[j][i]){    //第j盞燈也會對第i盞燈產生影響；
                rep1(k,i,var)
                    a[j][k] ^= a[i][k];
            }
        }
    }
    if(free_var != 0) return free_var;
    rep_1(i,var-1,0){
        x[i] = a[i][var];
        rep0(j,i+1,equ)
            x[i] ^= (a[i][j] && x[j]);  //第j個燈會影響到第i盞燈，同時第j盞燈也會亮。
    }
}
void init()
{
    int i,j,k;
    rep0(i,0,5)
        rep0(j,0,6){
            int x = i*6+j;
            a[x][x] = 1;
            rep0(k,0,4){
                int nx = i + dir[0][k] ,ny = j + dir[1][k];
                int pos = nx*6+ny;
                if(nx < 0 || nx >= 5 || ny < 0 || ny >= 6) continue;
                a[pos][x] = 1;  //本來是對稱的矩陣，因為影響是相互的，但是寫成[x][pos]思想就不一樣了
            }
        }
}
int main()
{
    int T,kase = 1,i;
    cin>>T;
    while(T--){
        MS0(x);MS0(a);
        rep0(i,0,30) scanf("%d",&a[i][30]);
        init();
        equ = var = 30;
        Guass();
        printf("PUZZLE #%d\n",kase++);
        rep0(i,0,30)
            printf("%d%c",x[i],(i+1)%6?' ':'\n');
    }
    return 0;
}