题目链接：POJ 1753
题意：
有一个4*4的方格，每个方格中放一粒棋子，这个棋子一面是白色，一面是黑色。游戏规则为每次任选16颗中的一颗，把选中的这颗以及它四周的棋子一并反过来，当所有的棋子都是同一个颜色朝上时，游戏就完成了。现在给定一个初始状态，要求输出能够完成游戏所需翻转的最小次数，如果初始状态已经达到要求输出0。如果不可能完成游戏，输出Impossible。
思路：
参照链接
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
/*
int dir[4][2] = { {1,0},{-1,0},{0,1}, {0,-1} };
void init()
{int i, j, x, y, t, temp;for (i = 0;i < 4;i++){for (j = 0;j < 4;j++){temp = 0;temp ^= (1 << ((3 - i) * 4 + 3 - j));for (t = 0;t < 4;t++){x = i + dir[t][0];y = j + dir[t][1];if (x < 0 || y < 0 || x>3 || y>3) continue;temp^= (1 << ((3 - x) * 4 + 3 - y));}cout << temp << " ";}cout << endl;}
}
*/struct Node {int state;int step;
}cur,nextnode;
bool vis[65536];
int change[16] = {51200,58368,29184,12544,35968,20032,10016,4880,2248,1252,626,305,140,78,39,19
};
int BFS(int state)
{memset(vis, false, sizeof(vis));queue<Node> q;cur.state = state;cur.step = 0;if (cur.state == 0||cur.state==0xffff) return cur.step;vis[state] = true;q.push(cur);while (!q.empty()){cur = q.front();q.pop();for (int i = 0;i < 16;i++){nextnode.state = cur.state^change[i];nextnode.step = cur.step + 1;if (nextnode.state == 0 || nextnode.state == 0xffff) return nextnode.step;if (vis[nextnode.state]) continue;vis[nextnode.state] = true;q.push(nextnode);}}return -1;
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endif//init();//由init（）获取change的值char ch[5][5];while (~scanf("%s", ch[0])){for (int i = 1;i < 4;i++)scanf("%s", ch[i]);int state = 0;for (int i = 0;i < 4;i++)for (int j = 0;j < 4;j++){state <<= 1;if (ch[i][j] == 'b') state += 1;}int ans = BFS(state);if (ans == -1) cout << "Impossible" << endl;else cout << ans << endl;}return 0;
}