http://poj.org/problem?id=1753
题意：有个4*4的棋盘，上面摆着黑棋和白旗，b代表黑棋，w代表白棋，现在有一种操作，如果你想要改变某一个棋子的颜色，那么它周围（前后左右）棋子的颜色都会被改变（白变成黑，黑变成白），问你将所有棋子变成白色或者黑色最少的步数。
思路：
1、如果用一个4*4的数组存储每一种状态，不但存储空间很大，而且在穷举状态时也不方便记录。因为每一颗棋子都只有两种状态，所以可以用二进制0和1表示每一个棋子的状态，则棋盘的状态就可以用一个16位的整数唯一标识。而翻转的操作也可以通过通过位操作来完成。显然当棋盘状态id为0（全白）或65535（全黑）时，游戏结束。
2、对于棋盘的每一个状态，都有十六种操作，首先要判断这十六种操作之后是否有完成的情况，如果没有，则再对这十六种操作的结果分别再进行上述操作，显然这里就要用到队列来存储了。而且在翻转的过程中有可能会回到之前的某种状态，而这种重复的状态是不应该再次入队的，所以维护 Visit[i]数组来判断 id==i 的状态之前是否已经出现过，如果不是才将其入队。如果游戏无法完成，状态必定会形成循环，由于重复状态不会再次入队，所以最后的队列一定会是空队列。
3、由于0^1=1，1^1=0，所以翻转的操作可以通过异或操作来完成，而翻转的位置可以通过移位来确定。
AC代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std; int change[] =
{
,,,,
,,,,
,,,,
,,,
};
bool visit[];
struct Node
{
int state;
int step;
};
int bfs(int state)
{
memset(visit,false,sizeof(visit));
queue<Node>q;
Node now,next;
now.state=state;
now.step=;
q.push(now);
visit[state]=true;
while(!q.empty())
{
now=q.front();
q.pop();
if(now.state== || now.state==0xffff)
return now.step;
for(int i=; i<; i++)
{
next.state = now.state^change[i];
next.step = now.step+;
if(visit[next.state]) continue;
if(next.state== || next.state==0xffff)
return next.step;
visit[next.state]=true;
q.push(next);
}
}
return -;
} int main()
{
char str[][];
int state,ans;
while(scanf("%s",str[])!=EOF)
{
for(int i=; i<; i++)
scanf("%s",str[i]);
state=;
for(int i=; i<; i++)
for(int j=; j<; j++)
{
state<<=;
if(str[i][j]=='b')
state+=;
}
ans=bfs(state);
if(ans==-) puts("Impossible");
else printf("%d\n",ans);
}
return ;
}