用16個為存儲棋盤的狀態(tài)，BFS時，每次枚舉所有可能的變換。
Source Code
| Problem: 1753 |
|
User: lovecanon |
| Memory: 732K |
|
Time: 32MS |
| Language: C |
|
Result: Accept |
- Source Code
-
#include<stdio.h>
#include<string.h>
unsigned int queue[65536],vis[65536],step[65536];
int main()
{
unsigned int i,j,k=1<<15,front=0,rear=0,cnt,tmp;
queue[++rear]=0;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
queue[rear]+=(getchar()=='b')*k;
k>>=1;
}
getchar();
}
if(queue[rear]==0||queue[rear]==65535) {printf("0\n");return 0;}
step[queue[rear]]=0;
memset(vis,0,sizeof(vis[0]));
vis[queue[rear]]=1;
while(front<rear)
{
cnt=queue[++front];
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
tmp=cnt;
if(i==0) tmp^=0x1<<(11-4*i-j);
else if(i==3) tmp^=0x1<<(19-4*i-j);
else {tmp^=0x1<<(19-4*i-j);tmp^=0x1<<(11-4*i-j);}
if(j==0) tmp^=0x3<<(14-4*i);
else if(j==3) tmp^=0x3<<(12-4*i);
else tmp^=0x7<<(14-4*i-j);
if(tmp==0||tmp==65535) {printf("%d\n",step[cnt]+1); return 0;}
else if(!vis[tmp])
{queue[++rear]=tmp; step[tmp]=step[cnt]+1;vis[tmp]=1;}
}
}
printf("Impossible\n");
return 0;
}