POJ 1222 EXTENDED LIGHTS OUT [高斯消元XOR]

题意:

$5*6$网格里有一些灯告诉你一开始开关状态,按一盏灯会改变它及其上下左右的状态,问最后全熄灭需要按那些灯,保证有解


经典问题

一盏灯最多会被按一次,并且有很明显的异或性质

一个灯作为一个方程一个变量

两盏灯相互影响系数设为1

常数项代表最后需不需要这盏灯改变状态

解这个异或方程组就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
const int N=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n=,_;
bitset<N> a[N];
void ini(){
for(int i=;i<=n;i++) a[i].reset();
}
char s[N];
void Gauss(){
int now=;
for(int i=;i<=n;i++){
int j=now;
while(j<=n&&!a[j][i]) j++;
if(now!=j) swap(a[now],a[j]);
for(int k=;k<=n;k++)
if(k!=now&&a[k][i]) a[k]^=a[now];
now++;
}
}
int main(){
freopen("in","r",stdin);
int T=read(),cas=;
while(T--){
for(int i=;i<=;i++)
for(int j=;j<=;j++){
int id=(i-)*+j;
a[id][id]=;
if(i!=) a[id][id-]=;
if(i!=) a[id][id+]=;
if(j!=) a[id][id-]=;
if(j!=) a[id][id+]=;
a[id][n+]=read();
}
Gauss();
printf("PUZZLE #%d\n",++cas);
for(int i=;i<=;i++)
for(int j=;j<=;j++)
_=(i-)*+j,printf("%d%c",a[_][n+]==?:,j==?'\n':' ');
}
}
上一篇:UGUI Button控件


下一篇:Elasticsearch 基础知识要点与性能监控