Poj 1222 EXTENDED LIGHTS OUT (高斯消元解异或方程组开关问题)

绝地灬酷狼 2022-09-17 12:25 88阅读 0赞

题意：有一个5\*6的矩阵，每个位置都表示按钮和灯，1表示亮，0表示灭。每当按下一个位置的按钮，它和它周围灯的状态全部翻转，问在这样的一个方阵中按下哪些按钮可以把整个方阵都变成灭的，这时1表示按了，0表示没按。

以下分析部分转自：http://blog.csdn.net/shiren\_Bod/article/details/5766907

这个游戏有一些技巧：  
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(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个按钮，和右下角的按钮，就

<table style="color:rgb(51,51,51)"> 
 <tbody> 
 <tr> 
 <td> 
 <div>
 能使L状态变成全灭状态。&nbsp; 
 对于固定行列的阵列来说，AA矩阵也是确定的。是否存在解，解是否唯一，只与AA矩阵有关。对于唯一解的情形，只要将LL乘以AA的逆矩阵即可。具体求AA的逆矩阵的方法，可以用高斯消元法。&nbsp; 
 </div> 
 <div> 
 由于是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）把矩阵&nbsp;转化为一个列向量，L也转化为一个列向量， 
 将sigma xi*Ai=Li&nbsp;对应位置的值相等就可以建立方程组了 
 X1*A(1,1)1+X2*A(1,2)1+X3*A(1,3)1+…………X30*A(30,30)1=L1;&nbsp;&nbsp;&nbsp;&nbsp;mod 2 
 X1*A(1,1)2+X2*A(1,2)2+X3*A(1,3)2+…………X30*A(30,30)2=L2;&nbsp;&nbsp;&nbsp;&nbsp;mod 2 
 X1*A(1,1)3+X2*A(1,2)3+X3*A(1,3)3+…………X30*A(30,30)3=L3&nbsp;&nbsp;&nbsp;&nbsp;mod 2 
 ……. 
 ……. 
 ……. 
 X1*A(1,1)30+X2*A(1,2)30+X3*A(1,3)30+…………X30*A(30,30)30=L30;&nbsp;mod 2 
 其中A(i,j)k&nbsp;表示列向量A中第K个元素 
 这里的*表示点乘，Xi取(1,0)&nbsp;+表示模2加法，所以在高斯消元的时候可以用^异或运算 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

1个开关最多控制5个灯，在构造的矩阵中，a\[i\]\[j\]=1表示第i个开关可以影响到j号灯

构造出的矩阵如图：

![SouthEast][]

#include <cstdio>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int N=31;
 int a[N][N]; //系数矩阵
 int ans[N];
 
 /*
 解异或方程可以套用高斯消元法，只须将原来的加减操作替换成异或操作就可以
 两个方程的左边异或之后，它们的公共项就没有了。
 */
 
 void Debug ()
 {
 	for (int i=0;i<N-1;i++)
 		for (int j=0;j<N-1;j++)
 			printf (j==N-2?"%d\n":"%d ",a[i][j]);
 }
 
 void Gauss ()
 {
 	int i,j,k;
 	for (k=0;k<30;k++)
 	{
 		i=k;
 		for (;i<30;i++)//对于k=0..N-1,找到一个M[i][k]不为0的行i
 			if (a[i][k]!=0)
 				break;
 		for (j=0;j<=30;j++) //把找到的第i行与第k行交换
 			swap (a[k][j],a[i][j]);
 /*用第k行去异或下面所有M[i][j]不为0的行i,消去它们的第k个系数,这样就将原矩阵化成了上三角矩阵
 最后一行只有一个未知数，这个未知数就已经求出来了，
 用它跟上面所有含有这个未知数的方程异或，就消去了所有的着个未知数，
 此时倒数第二行也只有一个未知数，它就被求出来了，用这样的方法可以自下而上求出所有未知数。
 */
 		for (i=0;i<30;i++)
 			if (k!=i && a[i][k])
 				for (j=0;j<=30;j++) // <= 
 					a[i][j]=a[k][j]^a[i][j];
 	}
 	for (i=0;i<30;i++)
 		ans[i]=a[i][30];
 }
 
 int main ()
 { 
 #ifdef ONLINE_JUDGE
 #else
 	freopen("read.txt","r",stdin);
 #endif
 	int T,i;
 	scanf("%d",&T);
 	for (int Cas=1;Cas<=T;Cas++)
 	{
 		memset(a,0,sizeof(a));
 		memset(ans,0,sizeof(ans));
 		for (i=0;i<30;i++)
 		{
 			scanf("%d",&a[i][30]);
 			ans[i]=0;
 		}
 		for (i=0;i<30;i++)
 		{
 			a[i][i]=1;
 			if (i%6!=0) a[i-1][i]=1; //
 			if (i%6!=5) a[i+1][i]=1;
 			if (i>5) a[i-6][i]=1;
 			if (i<24) a[i+6][i]=1;
 		}
 //		Debug();
 		Gauss();
 		printf ("PUZZLE #%d\n",Cas);
 		for (i=0;i<30;i++)
 			printf (i%6==5?"%d\n":"%d ",ans[i]);
 	}
 	return 0;
 }

[SouthEast]: /images/20220828/afbbb894c3cd461aaa073cc2ec2f8458.png