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