题目链接:http://poj.org/problem?id=1753

题意:经典开关问题,和poj1222一样,进行两次高斯消元即可,只用初始化的时候改一下初始状态。可能存在无解或多解的情况,多解要枚举自由变元的所有状态。

AC代码:

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std; const int maxn=;
const int inf=0x3f3f3f3f;
int mp[][],a[maxn][maxn],x[maxn],equ,var,free_x[maxn];
char s[]; void init(int p){
memset(a,,sizeof(a));
for(int i=;i<;++i){
for(int j=;j<;++j){
int t=i*+j;
a[t][]=p^mp[i][j];
a[t][t]=;
if(i>) a[t][(i-)*+j]=;
if(i<) a[t][(i+)*+j]=;
if(j>) a[t][i*+j-]=;
if(j<) a[t][i*+j+]=;
}
}
} int Gauss(){
int r=,cnt=;
for(int c=;r<equ&&c<var;++r,++c){
int Maxr=r;
for(int i=r+;i<equ;++i){
if(abs(a[i][c])>abs(a[Maxr][c]))
Maxr=i;
}
if(Maxr!=r){
for(int i=c;i<var+;++i)
swap(a[r][i],a[Maxr][i]);
}
if(!a[r][c]){
--r;
free_x[cnt++]=c;
continue;
}
for(int i=r+;i<equ;++i){
if(!a[i][c]) continue;
for(int j=c;j<var+;++j)
a[i][j]^=a[r][j];
}
}
for(int i=r;i<equ;++i)
if(a[i][var])
return -;
return var-r;
} int solve(int t){
int ret=inf;
for(int i=;i<(<<t);++i){
int cnt=;
memset(x,,sizeof(x));
for(int j=;j<t;++j){
if((i>>j)&){
++cnt;
x[free_x[j]]=;
}
}
for(int j=var-t-;j>=;--j){
int tmp=a[j][var],tp,ok=;
for(int k=j;k<var;++k){
if(!a[j][k]) continue;
if(ok){
ok=;
tp=k;
}
else{
tmp^=x[k];
}
}
x[tp]=tmp;
cnt+=x[tp];
}
ret=min(ret,cnt);
}
return ret;
} int main(){
equ=var=;
for(int i=;i<;++i){
scanf("%s",s);
for(int j=;j<;++j)
if(s[j]=='b') mp[i][j]=;
else mp[i][j]=;
}
init();
int t1,t2,t3,t4;
t1=Gauss();
if(t1!=-) t2=solve(t1);
init();
t3=Gauss();
if(t3!=-) t4=solve(t3);
if(t1==-&&t3==-)
printf("Impossible\n");
else
printf("%d\n",min(t2,t4));
return ;
}

最新文章

  1. C#操作剪贴板
  2. LeetCode:Text Justification
  3. Codeforces Round #373 (Div. 1)
  4. 【C#4.0图解教程】笔记(第19章~第25章)
  5. 如何在安卓/data(而不是/data/data)目录下进行文件的读写操作
  6. 3DShader之移位贴图(Displacement Mapping)
  7. 《Programming WPF》翻译 第5章 6.触发器
  8. artdialog关闭弹出窗口
  9. cv2.cornerHarris()详解 python+OpenCV 中的 Harris 角点检测
  10. 使用Java面向对象单词必备
  11. Android——媒体库 相关知识总结贴
  12. jfinal集成cas单点认证实践
  13. Haskell语言练习
  14. 第三次spring冲刺2
  15. async 和 await的前世今生 (转载)
  16. Nuget~打包时添加powershell初始化脚本
  17. liunx less 命令
  18. 对于&quot;第一次创业者&quot;应该给什么样的建议
  19. yii2:oracle date类型字段的写入或查询
  20. Python之virtualenv沙盒环境

热门文章

  1. 008_Linux驱动之_IO口的配置
  2. SSH远程连接排错的过程
  3. gcc 带参数进行编译
  4. python 识别鼠标左键点击
  5. 单词拼接(dfs/回溯/递归)
  6. Linux设备驱动程序 之 内存池
  7. Python 自学笔记(五)
  8. java中json的使用和解析
  9. Vue UI组件库
  10. 用jeecg做个项目第三讲(自定义导入导出)