给出4*4的黑白棋盘
可以对任意一个点进行翻转（黑->白，或 白->黑），同时会翻转其相邻的四个点
问最少的步骤使棋盘变成全黑或者全白，状压存状态即可
#include "stdio.h"#include "string.h"#include "queue"using namespace std;int dir[5][2]={ {1,0},{-1,0},{0,1},{0,-1},{0,0} };char str[10][10];int b[4][4]={ {1,2,4,8}, {16,32,64,128}, {256,512,1024,2048}, {4096,8192,16384,32768}};int used[100010];int bfs(){queue<int>q;int cur,next;int i,j,x,y,l;cur=0;for (i=0;i<4;i++)for (j=0;j<4;j++)if (str[i][j]=='b')cur+=b[i][j];q.push(cur);if (cur==0 || cur==65535) return 0;memset(used,-1,sizeof(used));used[cur]=0;while (!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++)for (j=0;j<4;j++){next=cur;for (l=0;l<5;l++){x=i+dir[l][0];y=j+dir[l][1];if (x<0 || x>=4 || y<0 || y>=4) continue;next^=b[x][y];}if (next==0 || next==65535) return used[cur]+1;if (used[next]==-1){used[next]=used[cur]+1;q.push(next);}}}return -1;}int main(){int i,ans;while (scanf("%s",str[0])!=EOF){for (i=1;i<4;i++)scanf("%s",str[i]);ans=bfs();if (ans==-1)printf("Impossible\n");elseprintf("%d\n",ans);}return 0;}
，在那里，有我们特有的记忆，亲情之忆、
