poj 1222 EXTENDED LIGHTS OUT(高斯消元)

由于是0、1矩阵，上述方程也可以写成：

将1式两边同时加上一个L矩阵就可以变成
x(1,1)*A(1,1) + x(1,2)*A(1,2) + x(1,3)*A(1,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = L

A（1，1）把矩阵 转化为一个列向量，L也转化为一个列向量，

将sigma xi*Ai=Li 对应位置的值相等就可以建立方程组了

X1*A(1,1)1+X2*A(1,2)1+X3*A(1,3)1+…………X30*A(30,30)1=L1;    mod 2

X1*A(1,1)2+X2*A(1,2)2+X3*A(1,3)2+…………X30*A(30,30)2=L2;    mod 2

X1*A(1,1)3+X2*A(1,2)3+X3*A(1,3)3+…………X30*A(30,30)3=L3    mod 2

…….

…….

…….

X1*A(1,1)30+X2*A(1,2)30+X3*A(1,3)30+…………X30*A(30,30)30=L30; mod 2

其中A(i,j)k 表示列向量A中第K个元素

这里的*表示点乘，Xi取(1,0) +表示模2加法，所以在高斯消元的时候可以用^异或运算

首先，我们可以把6*5个灯组成的矩阵看成是一个1*30的向量a 。

然后，对于每一个开关 i ，我们也构造一个1*30的向量d（i），一个开关最多控制5个灯，其中开关状态改变则为1，不改变就为0，这样我们可以把30个开关的向量组成一个30*30的矩阵。

我们在构造一个30*1的向量ans，也就是我们要求的结果，ans[ i ]为1，表示需要按下第 i个开关，0表示不需要。这样ans*d=a（mod 2），（d 是30*30 的矩阵）就转化为解方程的问题了。

至于解方程，就没什么可说的了，就是用线代里面讲的方法就可以了。因为这里要模2，所以可以我们可以直接用计算机的异或运算。

#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#define LL long long
#define _LL __int64

using namespace std;
const int INF = 0x3f3f3f3f;

int a[32][32];
int equ,var;
int ans[32];

void debug()
{
	for(int i = 0; i < 30; i++)
	{
		for(int j = 0; j <= 30; j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
}
//因为题目说肯定有解，这里没有判断无解和无穷解的情况
void Gauss()
{
	int i,j,row,col,max_r;
	int ta,tb;

	row = col = 0;

	while(row < 30 && col < 30)
	{
		for(i = row; i < equ; i++)
			if(a[i][col] != 0)
				break;

		if(i != row)
		{
			for(j = col; j < var+1; j++)
				swap(a[row][j], a[i][j]);
		}

		if(a[row][col] == 0)
		{
			col++;
			continue;
		}

		for(i = row+1; i < equ; i++)
		{
			if(a[i][col] == 0)
				continue;
			for(j = col; j < var+1; j++)
				a[i][j] ^= a[row][j];
		}
		row++;
		col++;
	}
	//注意求解的方法
	for(i = var-1; i >= 0; i--)
	{
		ans[i] = a[i][var];

		for(j = i+1; j < var; j++)
			ans[i] ^= (a[i][j] && ans[j]);
	}
}

int main()
{
	int test,i,j;
	int x,y,xx,yy;

	scanf("%d",&test);
	for(int item = 1; item <= test; item++)
	{
		for(i = 0; i < 30; i++)
			scanf("%d",&a[i][30]);

		//形成增广阵
		for(i = 0; i < 30; i++)
		{
			x = i/6;
			y = i%6;
			for(j = 0; j < 30; j++)
			{
				xx = j/6;
				yy = j%6;
				if(abs(x-xx) + abs(y-yy) <= 1)
					a[i][j] = 1;
				else a[i][j] = 0;
			}
		}

		equ = var = 30;

		//debug();
		Gauss();

		printf("PUZZLE #%d\n",item);
		for(i = 0; i < 30; i++)
		{
			printf("%d",ans[i]);
			if(i % 6 == 5)
				printf("\n");
			else printf(" ");
		}
	}

	return 0;
}