比赛 |
20121009 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
翻转游戏 |
最终得分 |
100 |
用户昵称 |
Makazeu |
运行时间 |
0.070 s |
代码语言 |
C++ |
内存使用 |
3.47 MiB |
提交时间 |
2012-10-09 20:13:54 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#define black 0
#define white 1
using namespace std;
const int MAXN=18;
typedef int array[MAXN];
array binary,yuan;char c;
int hash[100000]={0};
class Queue{public:int t;array num;};
inline void init()
{
binary[1]=1;
for(int i=2;i<=17;i++) binary[i]=binary[i-1]*2;
for(int i=1;i<=16;i++)
{
scanf("%c",&c);
while(c!='b' && c!='w') scanf("%c",&c);
if(c=='b') yuan[i]=black;
else yuan[i]=white;
}
}
inline int GetHashValue(array a)
{
int res=0;
for(int i=1;i<=16;i++) res=res+a[i]*binary[i];
return res;
}
queue<Queue> q;
inline void bfs()
{
Queue tmp,nxt;int nhash;
nhash=GetHashValue(yuan);
for(int i=1;i<=16;i++) tmp.num[i]=yuan[i];
tmp.t=0;hash[nhash]=1; q.push(tmp);
if((nhash==0) ||(nhash==binary[17]-1)) {printf("0\n");exit(0);}
while(q.size())
{
tmp=q.front(); q.pop();
for(int i=1;i<=16;i++)
{
nxt=tmp; nxt.num[i]=!nxt.num[i];
if(((i-1)%4)!=0) nxt.num[i-1]=!nxt.num[i-1];
if((i%4)!=0) nxt.num[i+1]=!nxt.num[i+1];
if(i>4) nxt.num[i-4]=!nxt.num[i-4];
if(i<13) nxt.num[i+4]=!nxt.num[i+4];
nhash=GetHashValue(nxt.num);
if(hash[nhash]==1) continue;
hash[nhash]=1; nxt.t++;
if((nhash==0) ||(nhash==binary[17]-1))
{
printf("%d\n",nxt.t);
while(q.size()) q.pop();
return;
} q.push(nxt);
}
}
printf("Impossible\n");
}
int main()
{
freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);
init();bfs();
return 0;
}