poj1753（位运算压缩状态+bfs）
题意：有个4*4的棋盘，上面摆着黑棋和白旗，b代表黑棋，w代表白棋，现在有一种操作，如果你想要改变某一个棋子的颜色，那么它周围（前后左右）棋子的颜色都会被改变（白变成黑，黑变成白），问你将所有棋子变成白色或者黑色最少的步数。
思路：状态压缩+搜索。对于
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int t[20]={
51200,58368,29184,12544,
35968,20032,10016,4880,
2248,1252,626,305,
140,78,39,19,
};
int M=1<<16;
bool vist[(1<<16)];
struct node
{
int k;
int step;
};
void bfs(int ans)
{
queue<node>q;
node p;
p.k=ans;
p.step=0;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
if(p.k==0||p.k==(M-1))
{
printf("%d
",p.step);
return;
}
for(int i=0;i<16;i++)
{
node p1;
p1.step=p.step+1;
p1.k=p.k^t[i];
if(!vist[p1.k])
{
vist[p1.k]=true;
q.push(p1);
}
}
}
printf("Impossible
");
}
int main()
{
int ans=0,cnt=15;
for(int i=0;i<4;i++)
{
char ch[10];
scanf("%s",ch);
for(int j=0;j<4;j++)
{
if(ch[j]=='w')
{
ans|=(1<<cnt);
}
cnt--;
}
}
memset(vist,false,sizeof(vist));
vist[ans]=true;
bfs(ans);
return 0;
}