做题感悟：开始没好好读题，认为单个棋子也可以翻，那样的话就不可能出现 Impossible 的情况了，这说明没好好读题，既然题目给出 Impossible 那一定会有用，先用 dfs 暴力做的，然后看到网上有人用状态压缩，唉，我怎么没想到呢！（应该反思一下，毕竟也是做过几个状态压缩题的人，竟然没想到。）只能说一句：状态压缩太神奇了!
解题思路：因为题目只有 16 个位，所以转化为二进制没问题（和HDU 翻纸牌差不多）。这样图就可以标记了。
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std ;
char s[6] ;
bool vis[150005] ;
int p[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072} ;
struct zhang
{
int x,step ;
} ;
int search(int x,int temp) // 变化上下左右
{
if(x+4<16) // 下
temp^=p[x+4] ;
if(x-4>=0) // 上
temp^=p[x-4] ;
if(x%4>0) //右
temp^=p[x-1] ;
if(x%4<3) // 左
temp^=p[x+1] ;
return temp ;
}
int bfs(int sum)
{
int temp ;
queue<zhang>q ;
zhang curt,next ;
memset(vis,false,sizeof(vis)) ;
curt.x=sum ;
curt.step=0 ;
vis[sum]=true ;
q.push(curt) ;
while(!q.empty())
{
curt=q.front() ;
if(!curt.x||curt.x==65535)
return curt.step ;
q.pop() ;
for(int i=0 ;i<16 ;i++)
{
next.step=curt.step+1 ;
temp=curt.x^p[i] ;
temp=search(i,temp) ;
if(vis[temp])
continue ;
next.x=temp ;
vis[temp]=true ;
q.push(next) ;
}
}
return -1 ;
}
int main()
{
int i,j,sum=0 ;
for(i=0 ;i<4 ;i++)
{
scanf("%s",s) ;
for(j=0 ;j<4 ;j++)
if(s[j]=='b') // 压缩图
sum=sum^p[i*4+j] ;
}
int mx=bfs(sum) ;
if(mx!=-1)
printf("%d\n",mx) ;
else printf("Impossible\n") ;
}