题意:有一个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个按钮,和右下角的按钮,就
能使L状态变成全灭状态。
对于固定行列的阵列来说,AA矩阵也是确定的。是否存在解,解是否唯一,只与AA矩阵有关。对于唯一解的情形,只要将LL乘以AA的逆矩阵即可。具体求AA的逆矩阵的方法,可以用高斯消元法。 由于是0、1矩阵,上述方程也可以写成: 将1式两边同时加上一个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加法,所以在高斯消元的时候可以用^异或运算 |
1个开关最多控制5个灯,在构造的矩阵中,a[i][j]=1表示第i个开关可以影响到j号灯
构造出的矩阵如图:
#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; }