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

#include<fstream>
#include<queue>
using namespace std;
struct yu
{
	int v;
	bool f[5][5];
};
bool ck[100000000];
queue<yu>dq;
yu tmp;
int p,q;
bool check()
{
	bool flag;
	flag=tmp.f[1][1];
	for(p=1;p<=4;p++)
		for(q=1;q<=4;q++)
			if(tmp.f[p][q]!=flag)
				return 0;
	return 1;
}
int main(void)
{
	ifstream fin("flip.in");
	ofstream fout("flip.out");
	int i,j;
	char ch[4];
	for(i=1;i<=4;i++)
	{
		fin>>ch;
		for(j=0;j<4;j++)
			if(ch[j]=='b')
				tmp.f[i][j+1]=1;	
	}
	if(check())
				{
					fout<<tmp.v;
					return 0;
				}
	dq.push(tmp);
	while(dq.size())
	{
		for(i=1;i<5;i++)
			for(j=1;j<5;j++)
			{
				tmp=dq.front();
				tmp.f[i][j]=!tmp.f[i][j];
				tmp.f[i-1][j]=!tmp.f[i-1][j];
				tmp.f[i+1][j]=!tmp.f[i+1][j];
				tmp.f[i][j-1]=!tmp.f[i][j-1];
				tmp.f[i][j+1]=!tmp.f[i][j+1];
				tmp.v++;
				if(check())
				{
					fout<<tmp.v;
					return 0;
				}
				int n=0,m=1;
				for(p=1;p<=4;p++)
					for(q=1;q<=4;q++)
					{
						n+=(int)tmp.f[p][q]*m;
						m=m*2;
					}
				if(!ck[n])
				{
					dq.push(tmp);
					ck[n]=1;
				}
			}
		dq.pop();
	}
	fout<<"Impossible";
	fin.close();
	fout.close();
	return 0;
}