http://poj.org/problem?id=1753
题意：一个4*4的棋盘，只有黑和白两种棋子，每次翻转一个棋子，并且其四周的棋子也跟着翻转，求棋盘全为黑或全为白时所需的最少翻转次数。
思路：暴力枚举。
一共16个棋子，所以可以用二进制来存储。后来看了一下别人的代码，发现居然可以用异或运算来计算翻转情况，方便了不少。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; int t[] = { //对应翻转情况
, , , ,
, , , ,
, , , ,
, , , ,
}; int ans=;
bool vis[( << )]; struct node
{
int ans;
int step;
}; void bfs()
{
memset(vis, false, sizeof(vis));
queue<node>q;
node p;
p.ans = ans;
p.step = ;
q.push(p);
vis[ans] = true;
while (!q.empty())
{
p = q.front();
q.pop();
if (p.ans == || p.ans == )
{
cout << p.step << endl;
return;
}
for (int i = ; i<; i++)
{
node p1;
p1.step = p.step + ;
p1.ans = p.ans^t[i];
if (vis[p1.ans]) continue;
vis[p1.ans] = true;
q.push(p1);
}
}
cout << "Impossible" << endl;
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int cnt = ;
for (int i = ; i<; i++)
{
char ch[];
cin >> ch;
for (int j = ; j<; j++)
{
if (ch[j] == 'w')
{
ans += ( << cnt); //转化为十进制
}
cnt--;
}
}
bfs();
return ;
}