记录编号	287735	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-08-02 13:47:36	内存使用	0.37 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int WHITE=0,BLACK=(1<<16)-1,maxn=(1<<16)+10;
struct node{
	int k,g;
	node(int kk=0,int gg=0):k(kk),g(gg){}
};
int bfs(int);
bool vis[maxn]={false};
inline int hash(int i,int j){
	return (i<<2)+j;
}
char c;
int k=0;
int main(){
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	for(int i=0;i<4;i++)for(int j=0;j<4;j++){
		scanf(" %c",&c);
		if(c=='w')k^=1<<hash(i,j);
	}
	k=bfs(k);
	if(k==-1)printf("Impossible");
	else printf("%d",k);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
int bfs(int k){
	queue<node>q;
	q.push(node(k,0));
	int kk;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.k==BLACK||t.k==WHITE)return t.g;
		if(vis[t.k])continue;
		vis[t.k]=true;
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				kk=t.k;
				kk^=1<<hash(i,j);
				if(i)kk^=1<<hash(i-1,j);
				if(j)kk^=1<<hash(i,j-1);
				if(i<3)kk^=1<<hash(i+1,j);
				if(j<3)kk^=1<<hash(i,j+1);
				if(vis[kk])continue;
				q.push(node(kk,t.g+1));
			}
		}
	}
	return -1;
}
/*
bwwb
bbwb
bwwb
bwww
Answer:
4
*/