題意：5*6的一個由燈組成的方陣 操作一個燈 周圍的上下左右四個燈會發生相應變化 即由滅變亮 由亮變滅 問如何操作使燈全滅。
本題方法：猛戳這裡
[cpp]
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int N=105;
int equ,var;
int a[N][N];
int x[N];
bool free_x[N];
int free_num;
void Debug()
{
int i,j;
for(i=0;i<equ;i++)
{
for(j=0;j<var+1;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
int absx(int x)
{
return x<0? -x:x;
}
int gcd(int a,int b)
{
return b? gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int Gauss()
{
int i,j,k;
int max_r;
int col;
int ta,tb;
int LCM,temp;
int free_x_num;
int free_index;
col=0;
for(k=0;k<equ&&col<var;k++,col++)
{
max_r=k;
for(i=k+1;i<equ;i++)
{
if(absx(a[i][col])>absx(a[max_r][col])) max_r=i;
}
if(max_r!=k)
{
for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);
}
if(a[k][col]==0)
{
k--;continue;
}
for(i=k+1;i<equ;i++)
{
if(a[i][col]!=0)
{
LCM=lcm(absx(a[i][col]),absx(a[k][col]));
ta=LCM/absx(a[i][col]);
tb=LCM/absx(a[k][col]);
if(a[i][col]*a[k][col]<0) tb=-tb;
for(j=col;j<var+1;j++)
a[i][j]=(a[i][j]*ta%2-a[k][j]*tb%2+2)%2;
}
}
}
//Debug();
for(i=k;i<equ;i++)
{
if(a[i][col]!=0) return -1;
}
if(k<equ)
{
for(i=k-1;i>=0;i--)
{
free_x_num=0;
for(j=0;j<var;j++)
{
if(a[i][j]!=0&&free_x[j])
{
free_x_num++;
free_index=j;
}
}
if(free_x_num>1) continue;
temp=a[i][var]%2;
for(j=0;j<var;j++)
{
if(a[i][j]!=0&&j!=free_index) temp-=a[i][j]*x[j];
}
x[free_index]=temp;
free_x[free_index]=0;
}
return var-k;
}
for(i=var-1;i>=0;i--)
{
temp=a[i][var]%2;
for(j=i+1;j<var;j++)
{
if(a[i][j]!=0) temp=(temp%2-a[i][j]*x[j]%2+2)%2;
}
if(temp%a[i][i]!=0) return -2;
x[i]=(temp/a[i][i])%2;
}
return 0;
}
int main()
{
int i,j,t,k=1;
scanf("%d",&t);
equ=30;var=30;
while(t--)
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
memset(free_x,1,sizeof(free_x));
for(i=0;i<5;i++)
{
for(j=0;j<6;j++)
{
if(i-1>=0) a[i*6+j][(i-1)*6+j]=1;
if(i+1<=4) a[i*6+j][(i+1)*6+j]=1;
if(j-1>=0) a[i*6+j][i*6+j-1]=1;
if(j+1<=5) a[i*6+j][i*6+j+1]=1;
a[i*6+j][i*6+j]=1;
scanf("%d",&a[i*6+j][30]);
}
}
free_num=Gauss();
if(free_num==-1)
{
puts("No Answer!");
continue;
}
if(free_num==-2)
{
puts("With double but don't has integer solutions!");
continue;
}
if(free_num>=0)
{
int tt=0;
printf("PUZZLE #%d\n",k++);
for(i=0;i<var;i++)
{
tt++;
if(tt%6==0) printf("%d\n",x[i]);
else printf("%d ",x[i]);
}
}
}
return 0;
}
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int N=105;
int equ,var;
int a[N][N];
int x[N];
bool free_x[N];
int free_num;
void Debug()
{
int i,j;
for(i=0;i<equ;i++)
{
for(j=0;j<var+1;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
int absx(int x)
{
return x<0? -x:x;
}
int gcd(int a,int b)
{
return b? gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int Gauss()
{
int i,j,k;
int max_r;
int col;
int ta,tb;
int LCM,temp;
int free_x_num;
int free_index;
col=0;
for(k=0;k<equ&&col<var;k++,col++)
{
max_r=k;
for(i=k+1;i<equ;i++)
{
if(absx(a[i][col])>absx(a[max_r][col])) max_r=i;
}
if(max_r!=k)
{
for(j=k;j<var+1;j++) swap(a[k][j],a[max_r][j]);
}
if(a[k][col]==0)
{
k--;continue;
}
for(i=k+1;i<equ;i++)
{
if(a[i][col]!=0)
{
LCM=lcm(absx(a[i][col]),absx(a[k][col]));
ta=LCM/absx(a[i][col]);
tb=LCM/absx(a[k][col]);
if(a[i][col]*a[k][col]<0) tb=-tb;
for(j=col;j<var+1;j++)
a[i][j]=(a[i][j]*ta%2-a[k][j]*tb%2+2)%2;
}
}
}
//Debug();
for(i=k;i<equ;i++)
{
if(a[i][col]!=0) return -1;
}
if(k<equ)
{
for(i=k-1;i>=0;i--)
{
free_x_num=0;
for(j=0;j<var;j++)
{
if(a[i][j]!=0&&free_x[j])
{
free_x_num++;
free_index=j;
}
}
if(free_x_num>1) continue;
temp=a[i][var]%2;
for(j=0;j<var;j++)
{
if(a[i][j]!=0&&j!=free_index) temp-=a[i][j]*x[j];
}
x[free_index]=temp;
free_x[free_index]=0;
}
return var-k;
}
for(i=var-1;i>=0;i--)
{
temp=a[i][var]%2;
for(j=i+1;j<var;j++)
{
if(a[i][j]!=0) temp=(temp%2-a[i][j]*x[j]%2+2)%2;
}
if(temp%a[i][i]!=0) return -2;
x[i]=(temp/a[i][i])%2;
}
return 0;
}
int main()
{
int i,j,t,k=1;
scanf("%d",&t);
equ=30;var=30;
while(t--)
{
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
memset(free_x,1,sizeof(free_x));
for(i=0;i<5;i++)
{
for(j=0;j<6;j++)
{
if(i-1>=0) a[i*6+j][(i-1)*6+j]=1;
if(i+1<=4) a[i*6+j][(i+1)*6+j]=1;
if(j-1>=0) a[i*6+j][i*6+j-1]=1;
if(j+1<=5) a[i*6+j][i*6+j+1]=1;
a[i*6+j][i*6+j]=1;
scanf("%d",&a[i*6+j][30]);
}
}
free_num=Gauss();
if(free_num==-1)
{
puts("No Answer!");
continue;
}
if(free_num==-2)
{
puts("With double but don't has integer solutions!");
continue;
}
if(free_num>=0)
{
int tt=0;
printf("PUZZLE #%d\n",k++);
for(i=0;i<var;i++)
{
tt++;
if(tt%6==0) printf("%d\n",x[i]);
else printf("%d ",x[i]);
}
}
}
return 0;
}
