比赛 20121009 评测结果 AAWWAAAAAAAAAAAAAAAA
题目名称 翻转游戏 最终得分 90
用户昵称 Cloud 运行时间 0.106 s
代码语言 C++ 内存使用 12.81 MiB
提交时间 2012-10-09 20:22:04
显示代码纯文本
#include<fstream>
#include<queue>
using namespace std;
struct yu
{
	int v;
	bool f[5][5];
};
bool ck[10000000];
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;	
	}
	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=2;
				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;
}