|
EXTENDED LIGHTS OUT
Description
Lights Out就是下图的游戏,给你一个5*6的矩阵.
 你的目标是把灯全关上.  0表示关,1表示开. Input
第一行为数据组数T.
对于每组数据,输入1个5*6的矩阵.
Output
对于每组数据,输出一行 "PUZZLE #m".接下来为还原矩阵.
Sample Input 2 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 Sample Output PUZZLE #1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 PUZZLE #2 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 Source |
就是Gauss消元的xor版本.
显然若 a1 xor a2 xor a3..=an
b1 xor b2 xor b3..=bn
则 (a1 xor b1) xor (a2 xor b2)..=an xor an
满足消元性质
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
const int n=5,m=6;
bool inside(int x){return (x>=0)&&(x<31);}
struct E
{
int a[31];
int& operator[](int p){static int t;if (inside(p)) return a[p]; else return t;}
friend E operator^(E a,E b)
{
for (int i=0;i<31;i++) a[i]^=b[i];
return a;
}
};
struct M
{
E a[30];
E& operator[](int p){return a[p];}
M()
{
// memset(a,sizeof(a),0);
for (int i=0;i<30;i++)
for (int j=0;j<31;j++) a[i][j]=0;
for(int i=0;i<n*m;i++)
{
a[i][i]=a[i][i+6]=a[i][i-6]=1;
if (i%6) a[i][i-1]=1;
if (i%6<5) a[i][i+1]=1;
}
}
void gauss()
{
int i=0,j=0,n=30,m=31;
while (i<n&&j<m)
{
// print();
int maxi=i;
for(int k=i+1;k<n;k++) if (a[k][j]>a[maxi][j]) maxi=k;
if (a[maxi][j]!=0)
{
swap(a[maxi],a[i]);
for(int k=i+1;k<n;k++)
if (a[k][j]!=0) a[k]=a[k]^a[i];
}
i++;j++;
}
for(int i=28;i>=0;i--)
{
for(int j=i+1;j<30;j++) if (a[i][j]) {a[i][j]=0;a[i][30]^=a[j][30]; }
}
for (int i=0;i<30;i++)
{
cout<<a[i][30];
if (i%6==5) cout<<endl; else cout<<' ';
}
}
void print()
{
for (int i=0;i<30;i++)
{
for (int j=0;j<31;j++) cout<<a[i][j]<<' ';
cout<<endl;
}
cout<<"--------------------------------------------------n";
system("pause");
}
}EM;
int main()
{
// freopen("poj1222.in","r",stdin);
int tt;
cin>>tt;
for(int t=1;t<=tt;t++)
{
EM=M();
for(int i=0;i<n*m;i++) cin>>EM[i][30];
cout<<"PUZZLE #"<<t<<endl;
EM.gauss();
}
return 0;
}
