首页 > 代码库 > POJ 1222 EXTENDED LIGHTS OUT（高斯消元解XOR方程组）
POJ 1222 EXTENDED LIGHTS OUT（高斯消元解XOR方程组）
http://poj.org/problem?id=1222
题意：
现在有5*6的开关，1表示亮，0表示灭，按下一个开关后，它上下左右的灯泡会改变亮灭状态，要怎么按使得灯泡全部处于灭状态，输出方案，1表示按，0表示不按。
思路：
每个开关最多只按一次，因为按了2次之后，就会抵消了。
可以从结果出发，也就是全灭状态怎么按能变成初始状态。
用3*3来举个例子，$X\left ( i,j \right )$表示这些开关是按还是不按，那么对于第一个开关，对它有影响的就只有2、4这两个开关，所以它的异或方程组就是：
$X\left ( 1,1 \right )*A\left ( 1,1 \right ) XOR X\left ( 2,2 \right )*A\left ( 2,2 \right )...XOR X\left ( 9,9 \right )*A\left ( 9,9 \right ) = $初始状态
这样一来就有30个异或方程组，高斯消元解一下即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 100 + 5;17 18 int ans[maxn];19 int c[maxn][maxn];20 21 void Gauss()22 {23 int i=0,j=0,k,r;24 for(k=0;k<30;k++) //现在处理第k行25 {26 i=k;27 while(c[i][k]==0 && i<30) i++; //找到一行第k列元素不为028 if(i!=k) for(j=0;j<=30;j++) //交换两行29 swap(c[k][j],c[i][j]);30 31 //消元与回代合并了32 for(i=0;i<30;i++) if(k!=i && c[i][k])33 for(j=k;j<=30;j++) c[i][j]=c[k][j]^c[i][j];34 }35 for(int i=0;i<30;i++)36 ans[i]=c[i][30];37 }38 39 int main()40 {41 //freopen("in.txt","r",stdin);42 int T;43 int kase=0;44 scanf("%d",&T);45 while(T--)46 {47 memset(c,0,sizeof(c));48 for(int i=0;i<30;i++) scanf("%d",&c[i][30]);49 50 for (int i=0;i<30;i++)51 {52 c[i][i]=1;53 if (i%6!=0) c[i-1][i]=1;54 if (i%6!=5) c[i+1][i]=1;55 if (i>5) c[i-6][i]=1;56 if (i<24) c[i+6][i]=1;57 }58 59 Gauss();60 printf ("PUZZLE #%d\n",++kase);61 for (int i=0;i<30;i++)62 printf (i%6==5?"%d\n":"%d ",ans[i]);63 }64 return 0;65 }
POJ 1222 EXTENDED LIGHTS OUT（高斯消元解XOR方程组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。