输出结果不对 大家看看哪错了
今日程序内容:
棋盘游戏。在一个4 x 4的棋盘上有 8个黑棋和 8个白棋,当且仅当两个格子有公共边,这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。给出一个初始棋盘和一个最终棋盘,请找出一个最短的移动序列使初始棋盘变为最终棋盘。
- 输入:
前四行,每行4个数字( 1或者0 ),描述了初始棋盘;接着是一个空行; 第六到第九行,每行 4个数字( 1或者0),描述了最终棋盘。
- 输出:
输出的第一行是一个整数n,表示最少的移动步数。
#include <stdio.h>
int A,B;
int vis[100000];
struct P
{
int num,d;
};
struct P p[100];
void bfs()
{
p[0].num=A,p[0].d=0;
while(p[0].num!=0)
{
int tmp=p[0].num;
int k=0;
if(tmp==B)
{
printf("%d\n",p[0].d);
return;
}
for(int i=15;i>=0;i--)
{
int x=(15-i)/4,y=(15-i)%4,w=1<<i,z;
if(y<3&&(tmp&(1<<i))!=(tmp&(1<<(i-1))))
{
z=1<<(i-1);
if(!vis[tmp^z^w])
{
vis[tmp^z^w]=1;
p[k++].num=tmp^z^w;
p[k++].d=p[0].d+1;
}
}
if(x<3&&(tmp&(1<<i))!=(tmp&(1<<(i-4))))
{
z=1<<(i-4);
if(!vis[tmp^z^w])
{
vis[tmp^z^w]=1;
p[k++].num=tmp^z^w;
p[k++].d=p[0].d+1;
}
}
}
}
}
int main()
{
int i;
char ch;
for(i=15;i>=0;i--)
{
scanf("%c",&ch);
if(ch=='1')
{
A+=1<<i;
}
}
getchar();
for(i=15;i>=0;i--)
{
scanf("%c",&ch);
if(ch=='1')
{
B+=1<<i;
}
}
printf("%d %d",A,B);
if(A==B)
{
printf("0\n");
}
else
{
bfs();
}
return 0;
}