马的移动bfs
题目描述
zzq很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：
给定两个棋盘上的方格a和b，马从a跳到b最少需要多少步？
现请你编程解决这个问题。
给定两个棋盘上的方格a和b，马从a跳到b最少需要多少步？
现请你编程解决这个问题。
提示：国际象棋棋盘为8格*8格，马的走子规则为，每步棋先横走或直走一格，然后再往外斜走一格。
输入
输入包含多组测试数据。每组输入由两个方格组成，每个方格包含一个小写字母（a~h），表示棋盘的列号，和一个整数（1~8），表示棋盘的行号。
输出
对于每组输入，输出一行“To get from xx to yy takes n knight moves.”。
样例输入
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
样例输出
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
struct note
{
int x;
int y;
int f;
int s;
};int main()
{
struct note que[10100];
int a[111][111],book[111][111];
int next[8][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
char s,s2;
int t,i,j,k,n,m,x1,y1,p,q,tx,ty,flag;
int head,tail;
char s1[110][110];
while(scanf("\n%c%d %c%d",&s,&m,&s2,&n)!=EOF)
{
x1=s-96;
y1=m;
q=n;
p=s2-96;
memset(a,0,sizeof(a));
memset(book,0,sizeof(book));
//printf("x1x2 %d %d %d %d\n",x1,y1,p,q);
if(x1==p&&y1==q)
printf("To get from %c%d to %c%d takes 0 knight moves.\n",s,m,s2,n);
else
{
for(i=1;i<=8;i++)
{
for(j=1;j<=8;j++)
{
a[i][j]=0;
}
}
head=1;tail=1;
que[tail].x=x1;
que[tail].y=y1;
que[tail].f=0;
que[tail].s=0;
tail++; //因为que[1]已经存入了坐标需要+1.后面才能用
book[x1][y1]=1;//注意起点走过需要标记
flag=0;
while(head<tail)
{
for(k=0;k<=7;k++)
{
tx=que[head].x+next[k][0];
ty=que[head].y+next[k][1];
if(tx<1||tx>8||ty<1||ty>8)
continue;
if(a[tx][ty]==0&&book[tx][ty]==0)
{
book[tx][ty]=1;
que[tail].x=tx;
que[tail].y=ty;
que[tail].f=head;
que[tail].s=que[head].s+1;
tail++;
}
if(tx==p&&ty==q)
{
flag=1;
break;//此时结束的只是该层循环，外层循环仍在继续需要用flag标记一下结束外层循环
}
}
if(flag==1)
break;
head++;
}
printf("To get from %c%d to %c%d takes %d knight moves.\n",s,m,s2,n,que[tail-1].s);
}
}
return 0;
}
版权声明：本文为Gakki_wpt原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。