比赛 |
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);
}