题目链接: http://poj.org/problem?id=1222
题目大意：一堆开关，或开或关。每个开关按下后，周围4个方向开关反转。问使最后所有开关都关闭的，开关按法。0表示不按，1表示按。
解题思路：
一共只有5*6个开关。
对于每个开关，设其最终状态为x5，上下左右四个开关最终状态分别为x1,x2,x3,x4,
那么有方程x1^x2^x3^x4^x5^初始状态=0。
这样就有30个方程。解这30个线性方程组即可。
用高斯消元法来解方程组，变化如下：
①对于原本找列中绝对值最大这一步，可以简化成找第一个为1的k，因为系数矩阵不是0就是1，最大就是1。
②原本的+号现在变成^号。
这里推荐一下cxlove神牛的简洁写法，他把col和row合二而一，又将解向量和系数矩阵合二为一，非常吊。
#include "cstdio"
#include "iostream"
using namespace std;
int ratio[][],dir[][]={,,-,,,,,-,,};
void reset()
{
for(int i=; i<; i++)
for(int j=; j<; j++)
for(int k=; k<; k++)
{
int x=i+dir[k][],y=j+dir[k][];
if (x>=&&y>=&&x<&&y<) ratio[i*+j][x*+y]=;
}
}
void guess()
{
for(int i=;i<;i++)
{
int k=i;
for(;k<;k++)
if(ratio[k][i]!=) break;
for(int j=;j<=;j++) swap(ratio[i][j],ratio[k][j]);
for(int j=;j<;j++)
{
if(i!=j&&ratio[j][i])
for(int k=;k<=;k++)
ratio[j][k]=ratio[i][k]^ratio[j][k];
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
int T,no=;
scanf("%d",&T);
while(T--)
{
printf("PUZZLE #%d\n",++no);
reset();
for(int i=;i<;i++) scanf("%d",&ratio[i][]);
guess();
for(int i=;i<;i++)
{
printf("%d",ratio[i][]);
if(i%==) printf("\n");
else printf(" ");
} }
}
| 13596495 | neopenx | 1222 | Accepted | 160K | 0MS | C++ | 1186B | 2014-11-04 00:51:23 |