题意简单，目标就是求把棋子按特定规则翻成一个颜色的最小步数。注意到以“中心棋子”为准，中心棋子翻n次皆等价于翻0/1次，最优解不可能使同一中心子翻大于1次，因此最优方案的每一步中心子都是互不相同的，由此题目沦为暴力枚举中心子的水题。。。。。
有很多人写了bfs+bit压缩，个人觉得以这题的数据量写那么华丽辛苦了。。。 暴力递归碾过：
1
#include<cstdio>
2#include<cstring>
3bool p[5][5],pt[5][5];
4
int dir[5][2]=
{ {0,0},{0,-1},{0,1},{1,0},{-1,0} };
5int w,b;
6int res,max;
7bool find;
8
9void dfs(int sou,int depth,int path[]){
10
int i,j,x,y,xx,yy,bt,wt;
11 if(find) return ;
12 path[depth]=sou;
13
if( depth >= max ){
14 wt=w; bt=b;
15 for(i=0;i<4;i++) for(j=0;j<4;j++) pt[i][j]=p[i][j];
16 for(i=1;i<=max;i++){
17 x=path[i]/4; y=path[i]%4;
18 for(j=0;j<5;j++){
19 xx=x+dir[j][0]; yy=y+dir[j][1];
20 if( xx+1 && 4-xx && yy+1 && 4-yy ){
21 if(pt[xx][yy]){ --bt; ++wt; }
22 else { ++bt; --wt; }
23 pt[xx][yy]=!pt[xx][yy];
24
}
25 }
26 }
27 if( bt == 16 | wt == 16 ) {
28 find = true; res=max;
29 }
30 return ;
31 }
32 else{
33 for(i=sou+1;i<=15-(max-(depth+1));i++) dfs(i,depth+1,path);
34 }
35
}
36
37int main(){
38 int i,j,depth;
39 char k;
40 int path[17];
41
42 for(i=0;i<4;i++,getchar())
43 for(j=0;j<4;j++){
44 scanf("%c",&k); p[i][j]=(k-'w')?1:0;
45 if(k-'w') ++b;
46 else ++w;
47 }
48 res=-1;
49 find=false;
50 for(max=0;max<=16;max++)
51 for(i=0;i<=15-(max-(0+1));i++)
52 if( !find ) dfs(i,1,path);
53 if( -1 == res ) printf("Impossible\n");
54 else printf("%d\n",res);
55
56 return 0;
57}