POJ 1222(Gauss消元xor版)

就是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;
}