记录编号	43356	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.070 s
提交时间	2012-10-09 23:03:55	内存使用	3.66 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#define black 0
#define white 1
using namespace std;
const int MAXN=18;
typedef int array[MAXN];
array binary,yuan;char c;
int hash[100000]={0};
class Queue{public:int t;array num;};

inline void init()
{
	binary[1]=1;
	for(int i=2;i<=17;i++) binary[i]=binary[i-1]*2;
	for(int i=1;i<=16;i++)
	{
		scanf("%c",&c);
		while(c!='b' && c!='w') scanf("%c",&c);
		if(c=='b') yuan[i]=black;
		else yuan[i]=white;
	}	
}

inline int GetHashValue(array a)
{
	int res=0;
	for(int i=1;i<=16;i++) res=res+a[i]*binary[i];
	return res;	
}
queue<Queue> q;
inline void bfs()
{
	Queue tmp,nxt;int nhash;
	nhash=GetHashValue(yuan);
	for(int i=1;i<=16;i++) tmp.num[i]=yuan[i];
	tmp.t=0;hash[nhash]=1; q.push(tmp);
	
	if((nhash==0) ||(nhash==binary[17]-1)) {printf("0\n");exit(0);}	
	while(q.size())
	{
		tmp=q.front(); q.pop(); 
		for(int i=1;i<=16;i++)
		{
			nxt=tmp; nxt.num[i]=!nxt.num[i];
			if(((i-1)%4)!=0) nxt.num[i-1]=!nxt.num[i-1];
			if((i%4)!=0) nxt.num[i+1]=!nxt.num[i+1];
			if(i>4) nxt.num[i-4]=!nxt.num[i-4];
			if(i<13) nxt.num[i+4]=!nxt.num[i+4];
			nhash=GetHashValue(nxt.num);
			if(hash[nhash]==1) continue;
			hash[nhash]=1; nxt.t++;
			if((nhash==0) ||(nhash==binary[17]-1))
			{
				printf("%d\n",nxt.t);
				while(q.size()) q.pop();
				return;
			} q.push(nxt);
		}
	}
	printf("Impossible\n"); 
}

int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	init();bfs();
	return 0;
}