poj 1222 EXTENDED LIGHTS OUT，poj1222
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;
}
View Code
