Description

Input

Output

Sample Input

e2 e4

a1 b2

b2 c3

a1 h8

a1 h7

h8 a1

b1 c3

f6 f6

Sample Output 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.
代码:

/*
简单BFS，寻找最短路径长度
*/
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
int m[10][10];//用来标记，避免重复，bfs常见剪枝
int ax,ay,bx,by;
struct nod
{
    int x,y;
    int step;
};
int f[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};
queue<nod> q;
int ans;
void  bfs()
{
    nod t;
    while(!q.empty())
    {
        t=q.front();
        m[t.x][t.y]=1;
        q.pop();
        if(t.x==bx&&t.y==by)
        {
            ans=t.step;
           return;
        }
        for(int i=0;i<8;i++)
        {
            int xx=t.x+f[i][0];
            int yy=t.y+f[i][1];
            nod n;
            n.x=xx,n.y=yy,n.step=t.step+1;
            if(xx>=1&&xx<=8&&yy>=1&&yy<=8&&!m[xx][yy])
                q.push(n);
        }
    }
}
int main()
{
    char a,c;
    int b,d;
    while(scanf("%c%d %c%d",&a,&b,&c,&d)!=EOF)//输入的时候需要注意，如果一个一个输入，中间加空格，也可以用两个字符串格式化输入（空格截止）
    {
        getchar();
        memset(m,0,sizeof(m));
         ax=b,ay=a-'a'+1;
         bx=d,by=c-'a'+1;//sb的我重复定义
        //cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<endl;
        nod k;
        k.x=ax,k.y=ay,k.step=0;
        q.push(k);
        bfs();
        cout<<"To get from "<<a<<b<<" to "<<c<<d<<" takes "<<ans<<" knight moves."<<endl;
            while(!q.empty())
        q.pop();//对于有多组数据情况，一定要记得清空队列
    }
    return 0;
}