比赛 20121009 评测结果 C
题目名称 翻转游戏 最终得分 0
用户昵称 Truth.Cirno 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-10-09 22:21:31
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;

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

struct
{
	short/**/ a[5][5];
}que[200000];

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

bool dup(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];
	while (head>=tail&&head<=699900)
	{
		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 (dup(head))
					head--;
			}
		tail++;
	}
	cout<<"Impossible"<<endl;
	return(0);
}