传送门：点击打开链接
题意：给你一个5*6的矩阵，每个点上都有一个灯，按下f[i][j]的按钮，f[i][j]位置的灯的状态会改变，它上下左右的灯的状态也会改变（开变关，关变开）。现在给出这个矩阵的初始状态，输出按下哪些按钮，使所有的灯都关闭。
分析：
解法一（穷举法）：我们可以先二进制枚举第一行所有的翻转情况，才64种。之后第一行已经确定了，然后看第2行，如果第一行某个位置为1，那么在同一列的第2行这个位置必须反转。。（因为第一行已经确定，不能再反转了，而影响第一行的，也只有在同一列的第2行），这样我们可以确定了，前N-1行，全部为0，最后单独检查最后一行，是否全部为0。
解法二（高斯消元）：每个位置可以列出一个方程， 列出增广矩阵： 每个位置可以形成增广矩阵的一行， 每行都有30个系数 分别代表（0到29号灯）， 将 可以影响该位置改变的 位置（自己、上、下、左、右）对应的置1， 其余置0，这样就形成了30*30的系数矩阵。将初始状态置入最后一列，就形成了增广矩阵。这里是解亦或方程组，注意与解普通方程组的区别，把加减改成亦或，乘法改成&&，代码参考大牛写的。。。
代码：
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> using namespace std; int n,mp[10][10],tp[10][10],b[10][10]; int gb(int x,int y) { int s=b[x][y]; if(x>0) s+=b[x-1][y]; if(y>0) s+=b[x][y-1]; if(y<5) s+=b[x][y+1]; return s; } void sv() { for(int i=0;i<(1<<6);i++) { memset(tp,0,sizeof(tp)); for(int j=0;j<6;j++) { if( i&(1<<(5-j)) ) b[0][j]=1; else b[0][j]=0; } for(int j=0;j<6;j++) { int s=b[0][j]; if(j>0) s+=b[0][j-1]; if(j<5) s+=b[0][j+1]; if(s%2) tp[0][j]=1^mp[0][j]; else tp[0][j]=mp[0][j]; } for(int j=1;j<5;j++) { for(int k=0;k<6;k++) { if(tp[j-1][k]) b[j][k]=1; else b[j][k]=0; } for(int k=0;k<6;k++) { int sum=gb(j,k); if(sum%2) tp[j][k]=1^mp[j][k]; else tp[j][k]=mp[j][k]; } } int s=0; for(int j=0;j<6;j++) s+=tp[4][j]; if( s==0 ) { for(int j=0;j<5;j++){ for(int k=0;k<6;k++) { cout<<b[j][k]; if( k!=5 ) cout<<" "; } cout<<endl; } } } } int main() { cin>>n; for(int t=1;t<=n;t++) { for(int i=0;i<5;i++) for(int j=0;j<6;j++) cin>>mp[i][j]; cout<<"PUZZLE #"<<t<<endl; sv(); } return 0; }#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; int a[300][300]; /// 增广矩阵 int x[300]; /// 解 int free_x[300]; /// 标记是否为自由未知量 int n, m; void Gauss(int n, int m) /// n个方程 m个未知数 即 n行m+1列 { ///转换为阶梯形式 int col=0, k, num=0; for(k=0;k<n && col<m;k++, col++) {///枚举行 int max_r=k; for(int i=k+1;i<n;i++)///找到第col列元素绝对值最大的那行与第k行交换 if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; for(int j=col;j<m+1;j++)/// 与第k行交换 swap(a[k][j], a[max_r][j]); /* if(!a[k][col])// 说明该col列第k行以下全是0了 { k--; free_x[num++]=col; continue; } */ for(int i=k+1;i<n;i++)/// 枚举要删除的行 if(a[i][col]) for(int j=col;j<m+1;j++) a[i][j]^=a[k][j]; } /// 唯一解 回代 for(int i=m-1;i>=0;i--){ x[i]=a[i][m]; for(int j=i+1;j<m;j++) x[i]^=(a[i][j] && x[j]); } } void init(){ n=5, m=6; memset(a, 0, sizeof(a)); memset(x, 0, sizeof(x)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ int t=i*m+j; a[t][t]=1; if(i>0) a[(i-1)*m+j][t]=1; if(i<n-1) a[(i+1)*m+j][t]=1; if(j>0) a[i*m+j-1][t]=1; if(j<m-1) a[i*m+j+1][t]=1; } } int main(){ int t, ca=1; scanf("%d", &t); while(t--){ init(); for(int i=0;i<n*m;i++) scanf("%d", &a[i][n*m]); printf("PUZZLE #%d\n", ca++); Gauss(n*m, n*m); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ printf("%d", x[i*m+j]); if(j==5) printf("\n"); else printf(" "); } } return 0; }
