poj 1222 （高斯消元）

(1)高斯消元法求解 （ 适用于01方矩阵的问题，不适用在解线性方程组中）

<wbr>首先介绍一下怎样用高斯消元法解题！！</wbr>

这个游戏的名字叫做Lights Out。一个板子上面有MxN个按钮，按钮也是灯。每次按下一个按钮，这个按钮和它的上下左右相邻按钮将同时切换各自的亮灭状态。给你一个初始状态，请给出一种方法，按某些按钮，使得所有的灯都灭。

这个游戏有一些技巧：
1、按按钮的顺序可以随便。
2、任何一个按钮都最多需要按下1次。因为按下第二次刚好抵消第一次，等于没有按。

这个问题可以转化成数学问题。
一个灯的布局可以看成一个0、1矩阵。以3x3为例：
0 1 0
1 1 0
0 1 1
表示一个布局。其中0表示灯灭，1表示灯亮。
每次按下按钮（POJ1222）或者叫一个宿舍关灯（0998），可以看成在原矩阵上加（模2加，就是按位异或）上一个如下的矩阵：
0 1 0
1 1 1
0 1 0
上述矩阵中的1表示按下第2行第2列的按钮时，作用的范围。如果按左上角的按钮，就是：
1 1 0
1 0 0
0 0 0

我们记L为待求解的原始布局矩阵。A(i,j)表示按下第i行第j列的按钮时的作用范围矩阵。在上述例子中，
L=
0 1 0
1 1 0
0 1 1

A(1,1)=
1 1 0
1 0 0
0 0 0

A(2,2)=
0 1 0
1 1 1
0 1 0

假设x(i,j)表示：想要使得L回到全灭状态，第i行第j列的按钮是否需要按下。0表示不按，1表示按下。那么，这个游戏就转化为如下方程的求解：
L + x(1,1)*A(1,1) + x(1,2)*A(1,2) + x(1,3)*A(2,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = 0

其中x(i,j)是未知数。方程右边的0表示零矩阵，表示全灭的状态。直观的理解就是：原来的L状态，经过了若干个A(i,j)的变换，最终变成0:全灭状态。
由于是0、1矩阵，上述方程也可以写成：
x(1,1)*A(1,1) + x(1,2)*A(1,2) + x(1,3)*A(2,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = L

这是一个矩阵方程。两个矩阵相等，充要条件是矩阵中每个元素都相等。将上述方程展开，便转化成了一个9元1次方程组：
<wbr></wbr>

简单地记做：AA * XX = LL

这个方程有唯一解：
x(1,1) x(1,2) x(1,3)
x(2,1) x(2,2) x(2,3)
x(3,1) x(3,2) x(3,3)
=
1 1 1
0 0 0
0 0 1

也就是说，按下第一行的3个按钮，和右下角的按钮，就能使L状态变成全灭状态。

对于固定行列的阵列来说，AA矩阵也是确定的。是否存在解，解是否唯一，只与AA矩阵有关。对于唯一解的情形，只要将LL乘以AA的逆矩阵即可。具体求AA的逆矩阵的方法，可以用高斯消元法。

<wbr></wbr>

a[i][j]为1当且仅当且仅当第j个灯变化会影响到第i个灯变化。B[i] = 1表示第i个灯开始时不是
关着的（即第i个灯最后的结果是要变化）。

以上转http://blog.sina.com.cn/s/blog_6a16f43f0100m4t5.html

此题可以通过枚举第一行的状态，然后推下一行使前一行全灭的态，直到最后一行，如果最后一行全灭则此种法可以

贴自己代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
using namespace std;
int ma[10][10],a[40][40],ans[40];
void init()
{
	int i,j,k,x;
	for(i=0;i<5;i++)
		for(j=0;j<6;j++)
		{
			x=6*i+j;
			a[x][x]=1;
			if(i-1>=0){
				k=6*(i-1)+j;
				a[x][k]=1;
			}
			if(i+1<5){
				k=6*(i+1)+j;
				a[x][k]=1;
			}
			if(j-1>=0){
				k=6*i+j-1;
				a[x][k]=1;
			}
			if(j+1<6){
				k=6*i+j+1;
				a[x][k]=1;
			}
		}
}
int gauss(int epu,int var)
{
	int i,j,k,col;
	int max_r;
//	num=0;
	for(k=0,col=0;k<epu&&col<var;col++)
	{
		max_r=k;
		for(i=k+1;i<30;i++)
			if(a[i][col]>a[max_r][col])
				max_r=i;
		if(a[max_r][col]!=0)
		{
		if(max_r!=k)
		{
			for(i=col;i<var+1;i++)
				swap(a[k][i],a[max_r][i]);
		}
		for(i=0;i<30;i++)
			if(i!=k&&a[i][col]!=0)
			for(j=col;j<=30;j++)
				a[i][j]^=a[k][j];
		k++;
		}
	}
//	for(i=0;i<30;i++)
//	{
//		for(j=0;j<=30;j++)
//			printf("%d ",a[i][j]);
//		printf("\n");
//	}
	for(i=0;i<30;i++)
	if(a[i][30])
	{
		for(j=0;j<30&&!a[i][j];j++);
		if(j==30)return 0;
		else
			ans[j]=a[i][30];
		
	}
	return 0;
}
int main()
{
	int t,i,j,k;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		memset(a,0,sizeof(a));
		init();
		for(i=0;i<5;i++)
			for(j=0;j<6;j++)
			{
				scanf("%d",&ma[i][j]);
				if(ma[i][j]==1)
					a[6*i+j][30]=1;
			}
//		for(i=0;i<30;i++)
//		{
//			for(j=0;j<=30;j++)
//				printf("%d ",a[i][j]);
//			printf("\n");
//		}
		memset(ans,0,sizeof(ans));
		gauss(30,30);
		printf("PUZZLE #%d\n",k); 
		for(i=0;i<5;i++)
		{
			for(j=0;j<5;j++)
				printf("%d ",ans[6*i+j]);
			printf("%d\n",ans[6*i+j]);
		}
	}
}