记录编号	43349	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2010冲刺七]翻转游戏	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	2.880 s
提交时间	2012-10-09 22:27:07	内存使用	8.97 MiB

#include <iostream>
#include <cstdio>
using namespace std;

const int RUL[5][2]={{0,0},{0,1},{0,-1},{-1,0},{1,0}};

struct
{
	bool a[5][5];
}que[200000];

int r[200000],deep[200000];
char cht[10];

bool dupped(int pos)
{
	int i;
	for (i=1;i<pos;i++)
		if (r[pos]==r[i])
			return(1);
	return(0);
}

int main(void)
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	int i,j,k,l,tail=0,head=0,tar0=0,tar1=65535,x,y;
	for (i=1;i<=4;i++)
	{
		cin>>cht;
		for (j=1;j<=4;j++)
			if (cht[j-1]=='b')
				que[0].a[i][j]=0;
			else
				que[0].a[i][j]=1;
	}
	for (i=1;i<=4;i++)
		for (j=1;j<=4;j++)
			r[0]=(r[0]<<1)+que[0].a[i][j];
	if (tar0==r[0]||tar1==r[0])
	{
		cout<<0<<endl;
		return(0);
	}
	while (head>=tail&&head<=199900)
	{
		for (i=1;i<=4;i++)
			for (j=1;j<=4;j++)
			{
				head++;
				que[head]=que[tail];
				for (k=0;k<5;k++)
				{
					x=RUL[k][0]+i;
					y=RUL[k][1]+j;
					if (x>=1&&x<=4&&y>=1&&y<=4)
						que[head].a[x][y]=!que[head].a[x][y];
				}
				r[head]=0;
				for (k=1;k<=4;k++)
					for (l=1;l<=4;l++)
						r[head]=(r[head]<<1)+que[head].a[k][l];
				deep[head]=deep[tail]+1;
				if (tar0==r[head]||tar1==r[head])
				{
					cout<<deep[head]<<endl;
					return(0);
				}
				if (dupped(head))
					head--;
			}
		tail++;
	}
	cout<<"Impossible"<<endl;
	return(0);
}