首页 > 代码库 > POJ 1222 高斯消元更稳
POJ 1222 高斯消元更稳
大致题意：
有5*6个灯，每个灯只有亮和灭两种状态，分别用1和0表示。按下一盏灯的按钮，这盏灯包括它周围的四盏灯都会改变状态，0变成1,1变成0。现在给出5*6的矩阵代表当前状态，求一个能全部使灯灭的解。
分析：
题目已经提示我们，按两次和按零次是一样的效果，所以每个灯的解为0或者1。这样我们可以构造一个30*30的方程组，右边的常数列为灯的初始状态。
影响当前灯的状态的按钮有5个
a[i][j]+x[i][j]+x[i][j-1]+x[i-1][j]+x[i][j+1]+x[i][j+1]=0 (mod 2)
x[i][j]+x[i][j-1]+x[i-1][j]+x[i][j+1]+x[i][j+1]=a[i][j] (mod 2)
不难发现，灯的初始状态只影响常数列，与系数矩阵无关，系数矩阵是不变的。
消元的过程中系数也可以对2取模，按n次与按n+2次的效果是一样的。对2取模更方便的运算就是异或了。
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;int n=30;int a[35][35],x[35];int mat[35][35];void init()//初始化系数矩阵{ int dx[]= {0,0,-1,0,1}; int dy[]= {0,-1,0,1,0}; for(int i=1; i<=5; i++) { for(int j=1; j<=6; j++) { for(int k=0; k<5; k++) { int x=i+dx[k]; int y=j+dy[k]; if(x>0 && x<=5 && y>0 && y<=6) mat[(i-1)*6+j][(x-1)*6+y]=1; } } }}void Gauss(int equ,int var){ int row,col; row=col=1; while(row<=equ && col<=var) { //列非零主 int r=row; for(int i=row; i<=equ; i++) if(a[i][col]!=0) { r=i; break; } if(r!=row) { for(int i=col; i<=var+1; i++) swap(a[row][i],a[r][i]); } 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+1; j++) a[i][j]^=a[row][j]; } row++; col++; } for(int i=equ; i>=1; i--) { x[i]=a[i][var+1]; for(int j=i+1; j<=var; j++) x[i]^=a[i][j]*x[j]; }}int main(){ int t,kase=1; scanf("%d",&t); init(); while(t--) { memset(a,0,sizeof(a)); for(int i=1; i<=30; i++) scanf("%d",&a[i][31]); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j]=mat[i][j]; Gauss(n,n); printf("PUZZLE #%d\n",kase++); for(int i=1; i<=5; i++) { for(int j=1; j<6; j++) printf("%d ",x[(i-1)*6+j]); printf("%d\n",x[i*6]); } } return 0;}
POJ 1222 高斯消元更稳
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。