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<queue>
#include<string>
#include<iostream>
#define INF 0xfffffff
using namespace std;
int sx,sy,ex,ey;
struct s
{
int x,y,step;
}a,temp;
int minn,v[10][10];
int dx[8]={1,1,2,2,-1,-1,-2,-2};
int dy[8]={2,-2,1,-1,-2,2,1,-1};
int jud(struct s a)
{
if(a.x<1||a.x>8||a.y<1||a.y>8)
return 0;
if(v[a.x][a.y])
return 0;
return 1;
}
void bfs()
{
queue<struct s>q;
a.x=sx;
a.y=sy;
a.step=0;
q.push(a);
v[sx][sy]=1;
while(!q.empty())
{
a=q.front();
q.pop();
for(int i=0;i<8;i++)
{
temp.x=a.x+dx[i];
temp.y=a.y+dy[i];
temp.step=a.step+1;
if(jud(temp))
{
if(temp.x==ex&&temp.y==ey)
{
if(temp.step<minn)
{
minn=temp.step;
}
}
v[temp.x][temp.y]=1;
q.push(temp);
}
}
}
}
int main()
{
char aa,c;
int b,d;
while(scanf("%c%d %c%d",&aa,&b,&c,&d)!=EOF)
{
getchar();
sx=aa-'a'+1;
ex=c-'a'+1;
sy=b;
ey=d;
memset(v,0,sizeof(v));
minn=INF;
bfs();
if(minn==INF)
minn=0;
printf("To get from %c%d to %c%d takes %d knight moves.\n",aa,b,c,d,minn);
}
}原文：http://blog.csdn.net/yu_ch_sh/article/details/44035253