题意：4*4的正方形，每个格子有黑白两面，翻转格子使得4*4个格子显示全黑或全白，翻转要求：选中的那个格子，以及其上下左右相邻的格子（如果存在）要同时翻转。输出最小的达到要求的翻转次数或者Impossible（如果不可能）
题目链接：http://poj.org/problem?id=1753
分析：因为每个格子只有黑白两面，所以对于每个格子来说，要么不翻转，要么翻转一次，因为翻转奇数次结果和翻转一次得到的效果是一样的，而翻转偶数次得到的效果和不翻转是一样的，则总共有16个格子，最多要翻转16次，每个格子有黑白两种颜色，假设每一次面临的4*4正方形代表一个状态，则总共有2^16种状态，可以用16位二进制数表示,每一位1代表'b'(白)，0代表'w'(黑)。当状态为（0或者65535）时则达到要求。
注意：1.因为只用求最少次数，用bfs做，将每一个没有访问到的状态 (用vis[]数组标记) 加入到队列中，如果游戏无法完成，状态必定会形成循环，由于重复状态不会再次入队，所以最后的队列一定会是空队列。当队列为空时说明此时还未达到要求，则是Impossible
2.二进制运算，翻转某一个格子即指将1变成0，0变成1.这里可以用异或运算的性质，1^0=1,0^0=0;所以只用将需要翻转的那个格子对应的16位二进制数的位置为1，其他不翻转的格子对应的16位二进制数的位置为0得到一个数和当前状态的16位二进制数异或即可得到翻转后的状态。
例如：
bwwb
bbwb
bwwb
bwww
的状态可以表示为1001 1101 1001 1000 (二进制)，如果我现在要翻转第一行第一个格子，则可以用此二进制数和1100 1000 0000 0000 异或，则可以得到下一个状态next=1001 1101 1001 1000 ^ 1100 1000 0000 0000 = 0101 0101 1001 1000
即：
wbwb
wbwb
bwwb
bwww
可以得到转换每一个格子需要异或的二进制数(十进制表示)：
int change[16] = {
51200,58368,29184,12544,
35968,20032,10016,4880,
2248,1252,626,305,
140,78,39,19
};
代码：
int dir[][]={{,},{-,},{,},{,-}};
void init()
{
int i,j,x,y,t,temp;
for(i=;i<;++i)
{
for(j=;j<;++j)
{
temp = ;
temp ^= (<<( - ( i* + j )));
for(t=;t<;++t)
{
x = i + dir[t][];
y = j + dir[t][];
if(x< || y< || x> || y>)
continue;
temp ^= (<<((-x)*+-y));
}
cout<<temp<<" ";
}
cout<<endl;
}
}
完整代码1：（bfs+bit）
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
char m[][];
//int di[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct Node
{
int state,step;
}nod[];
int vis[];
/*
int change[16] = //16种状态转换，对应4*4的翻子位置 方法2.直接异或得到状态
{
51200,58368,29184,12544,
35968,20032,10016,4880,
2248,1252,626,305,
140,78,39,19
};
*/
int getChang(int stat,int x,int y) //方法1.翻转需要翻转的格子
{
int tp=stat;
tp^=(<<(-x*-y));
if(x>) tp^=(<<(-(x-)*-y)); //上
if(x<) tp^=(<<(-(x+)*-y)); //下
if(y>) tp^=(<<(-x*-y+)); //左
if(y<) tp^=(<<(-x*-y-)); //右
return tp;
}
int bfs(Node cur)
{
queue<Node>q;
q.push(cur);
Node next;
vis[cur.state]=; while(!q.empty())
{
cur=q.front();
q.pop();
if(cur.state==||cur.state==) //判断是否全黑/全白
return cur.step;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
next.state=getChang(cur.state,i,j); //按部得到状态
//next.state=cur.state^change[i]; //直接异或得到状态 (循环要改为for(int i=0;i<16;i++) )
next.step=cur.step+;
if(next.state==||next.state==)
return next.step;
if(vis[next.state]) //是否已经入队过
continue;
q.push(next);
vis[next.state]=;
}
}
}
return -;
}
int main()
{
memset(vis,,sizeof(vis));
int tmp=;
for(int i=;i<;i++)
{
cin>>m[i];
for(int j=;j<;j++)
{
if(m[i][j]=='b')
tmp+=(<<(-*i-j));
}
}
Node cur;
cur.state=tmp;
cur.step=;
int ans=bfs(cur);
if(ans==-)
printf("Impossible\n");
else
printf("%d\n",ans);
return ;
}
完整代码2：（dfs）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int mp[][];
int step;
bool flag;
int judge()
{
for(int i=;i<;i++)
for(int j=;j<;j++)
if(mp[i][j]!=mp[][])
return ;
return ;
}
void flip(int x,int y)
{
mp[x][y]=!mp[x][y];
if(x>) mp[x-][y]=!mp[x-][y];
if(x<) mp[x+][y]=!mp[x+][y];
if(y>) mp[x][y-]=!mp[x][y-];
if(y<) mp[x][y+]=!mp[x][y+];
}
void dfs(int x,int y,int deep)
{
if(deep==step)
{
flag=judge();
return;
}
if(flag||x>=)
return;
flip(x,y);
if(y<)
dfs(x,y+,deep+);
else
dfs(x+,,deep+);
flip(x,y);
if(y%<)
dfs(x,y+,deep);
else
dfs(x+,,deep);
return;
}
int main()
{
string s;
flag=;
for(int i=;i<;i++)
{
cin>>s;
for(int j=;j<;j++)
if(s[j]=='b')
mp[i][j]=;
}
for(step=;step<=;step++)
{
dfs(,,);
if(flag)
break;
}
if(flag)
printf("%d\n",step);
else
printf("Impossible\n");
return ;
}