首页 > 代码库 > poj 1222 EXTENDED LIGHTS OUT(高斯消元)

poj 1222 EXTENDED LIGHTS OUT(高斯消元)

http://poj.org/problem?id=1222


先贴一个链接

http://blog.csdn.net/u013081425/article/details/24248247

枚举第一行的状态,进行试探,当最后一行都为0时,说明该方案可行。


还有一种方法是高斯消元。

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

这个游戏有一些技巧: 
1、按button的顺序能够随便。 
2、不论什么一个button都最多须要按下1次。由于按下第二次刚好抵消第一次,等于没有按。 

这个问题能够转化成数学问题。 
一个灯的布局能够看成一个0、1矩阵。以3x3为例: 
0 1 0 
1 1 0 
0 1 1 
表示一个布局。当中0表示灯灭,1表示灯亮。 
每次按下button(POJ1222)或者叫一个宿舍关灯(0998),能够看成在原矩阵上加(模2加,就是按位异或)上一个例如以下的矩阵: 
0 1 0 
1 1 1 
0 1 0 
上述矩阵中的1表示按下第2行第2列的button时,作用的范围。假设按左上角的button,就是: 
1 1 0 
1 0 0 
0 0 0 

我们记L为待求解的原始布局矩阵。A(i,j)表示按下第i行第j列的button时的作用范围矩阵。在上述样例中, 
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列的button是否须要按下。0表示不按,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) = 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(1,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = L 

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

简单地记做: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个button,和右下角的button,就

能使L状态变成全灭状态。 
对于固定行列的阵列来说,AA矩阵也是确定的。是否存在解,解是否唯一,仅仅与AA矩阵有关。对于唯一解的情形,仅仅要将LL乘以AA的逆矩阵就可以。详细求AA的逆矩阵的方法,能够用高斯消元法。

因为是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 <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>

#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;

int a[35][35];
int x[35];
int equ,var;

void init()
{
	memset(x,0,sizeof(x));
	memset(a,0,sizeof(a));
}


void Gauss()
{
	int row,col,i,j;
	row = col = 0;

	while(row < equ && col < var)
	{
		for(i = row; i < equ; i++)
			if(a[i][col] != 0)
				break;
		if(i != row)
		{
			for(j = col; j <= var; j++)
				swap(a[row][j],a[i][j]);
		}
		if(a[row][col] == 0)
		{
			col++;
			continue;
		}
		for(int i = row+1; i < equ; i++)
		{
			if(a[i][col] == 0) continue;
			for(int j = col; j <= var; j++)
				a[i][j] ^= a[row][j];
		}
		row++;
		col++;
	}
	for(i = var-1; i >= 0; i--)
	{
		x[i] = a[i][var];
		for(j = i+1; j < var; j++)
			x[i] ^= (a[i][j]&&x[j]);
	}
}

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

		for(int i = 0; i < 5; i++)
		{
			for(int j = 0; j < 6; j++)
			{
				int num = i*6+j;
				a[num][num] = 1;
				if(i >= 1)
					a[num-6][num] = 1;
				if(i <= 3)
					a[num+6][num] = 1;
				if(j - 1 >= 0)
					a[num-1][num] = 1;
				if(j + 1 <= 5)
					a[num+1][num] = 1;
			}
		}

		equ = 30;
		var = 30;

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