poj2965(位运算压缩+bfs+记忆路径)
题意：有个4*4的开关，里面有着16个小开关
-+-- ---- ---- '+'表示开关是关着的，'-'表示开关是开着的，只有所有的开关全被打开，总开关才会被打开。现在有一种操作，只要改变某个开关，那么这个开关的行列所在开关都会被改变 -+-- 问，要打开总开关至少要改变多少次开关？并输出改变开关的位置。
思路： 由于每个开关只有两种状态，那么对于这16个小开关，我们可以用2进制来压缩下，如果开关是打开的那么为'0'，如果是关着的，那么为'1'，如此，我们就可以从下到上，从右到左给这16个开关
标记状态，如果以某个点为中心，那么这个点的行列状态都压缩进去，遇到这个点，取反与不取反，然后一次广搜过去，再记忆下路径，结果就出来了......
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define M 1<<16 int t[20]={ 63624,62532,61986,61713, 36744,20292,12066,7953, 35064,17652,8946,4593, 34959,17487,8751,4383, }; structnode { int k; int step; }; structnode1 { int father; int x,y; }s[(1<<17)]; //bool vist[(1<<17)]; int sum; void print(int ans) { if(ans==sum) return; print(s[ans].father); printf("%d %d ",s[ans].x+1,s[ans].y+1); } void bfs(int ans) { queue<node>q; node p; p.k=ans; p.step=0; s[p.k].father=-10; q.push(p); while(!q.empty()) { p=q.front(); q.pop(); if(p.k==0) { printf("%d ",p.step); print(p.k); return; } for(int i=0;i<16;i++) { node p1; p1.k=p.k^t[i]; p1.step=p.step+1; if(s[p1.k].father==-1) { s[p1.k].father=p.k; s[p1.k].x=i/4; s[p1.k].y=i%4; q.push(p1); } } } } int main() { int ans=0,cnt=15; for(int i=0;i<4;i++) { char ch[100]; scanf("%s",ch); for(int j=0;j<4;j++) { if(ch[j]=='+') { ans|=(1<<cnt); } cnt--; } } //printf("%d ",ans); sum=ans; for(int i=0;i<(M);i++) { s[i].father=-1; } bfs(ans); return 0; }