比赛 20121009 评测结果 AAWAAAAAAAAAAAAAAAAA
题目名称 翻转游戏 最终得分 95
用户昵称 苏轼 运行时间 0.083 s
代码语言 C++ 内存使用 10.36 MiB
提交时间 2012-10-09 21:13:45
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
struct hehe
{
	int w[5][5];
	int deep;
}q[70000];
int e[70000]={0};
int f[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void bfs()
{
	if (e[0]==(1<<16)-1||e[0]==0)
	{
		cout<<0;
		exit(0);
	}
	else
	{
		int tou,wei;
		tou=wei=0;
		while (tou<=wei)
		{
			if (wei>65536)
			{
				cout<<"Impossible";
				exit(0);
			}
			for (int i=0;i<4;i++)
			{
				for (int j=0;j<4;j++)
				{
					int xx,yy;
					q[wei+1]=q[tou];
					q[wei+1].w[i][j]=1-q[tou].w[i][j];
					for (int k=0;k<4;k++)
					{
						xx=i+f[k][0];
						yy=j+f[k][1];
						if (xx>=0&&xx<4&&yy>=0&&yy<4)
						{
							q[wei+1].w[xx][yy]=1-q[tou].w[xx][yy];
						}
					}
					int tmp=0;
					for (int k=0;k<4;k++)
						for (int p=0;p<4;p++)
							tmp=(tmp<<1)+(q[wei+1].w[k][p]);
					bool temp=0;
					if (tmp==(1<<16)-1||tmp==0)
					{
						cout<<q[tou].deep+1;
						exit(0);
					}
					if (e[tmp])
						temp=1;
					if (!temp)
					{
						wei++;
						e[tmp]=1;
						q[wei].deep=q[tou].deep+1;
					}
				}
			}
			tou++;
		}
	}
}
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++)
		{
			char a;
			cin>>a;
			if (a=='w')
			{
				q[0].w[i][j]=0;
				e[0]=e[0]<<1;
			}
			if (a=='b')
			{
				q[0].w[i][j]=1;
				e[0]=e[0]<<1;
				e[0]=e[0]+1;
			}
		}
	}
	/*
	q[0].w[0][0]=1;
	q[0].w[0][1]=0;
	q[0].w[0][2]=1;
	q[0].w[0][3]=0;
	q[0].w[1][0]=0;
	q[0].w[1][1]=0;
	q[0].w[1][2]=0;
	q[0].w[1][3]=0;
	q[0].w[2][0]=1;
	q[0].w[2][1]=1;
	q[0].w[2][2]=0;
	q[0].w[2][3]=1;
	q[0].w[3][0]=1;
	q[0].w[3][1]=0;
	q[0].w[3][2]=0;
	q[0].w[3][3]=1;
	e[0]=41177;
	*/
	q[0].deep=0;
	e[e[0]]=1;
	bfs();
	cout<<"Impossible";
	return 0;
}