马的移动

小明很喜欢下国际象棋，一天，他拿着国际象棋中的“马”时突然想到一个问题：

给定两个棋盘上的方格A和B，马从A跳到B最少需要多少步？现请你编程解决这个问题。

提示：国际象棋棋盘为8格*8格，马的走子规则为，每步棋先横走或直走一格，然后再往外斜走一格。

输入

输入包含多组测试数据。

每组输入由两个方格组成，每个方格包含一个小写字母（a~h），表示棋盘的列号，和一个整数（1~8），表示棋盘的行号。

输出

对于每组输入，输出一行“To get from xx to yy takes n knight moves.”。

样例输入 Copy

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

样例输出 Copy

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，bfs需要用到queue，一般的bfs要搜的是一张图，如果要把图上的点放到queue中就需要用到结构体，所以先定义一个结构体，用来在queue中存储点；核心思路
就是把搜索到达的点（符合要求的点）放到queue中，然后出队，并把与他相关联的点入队，直到队列为空。这道题的难点在于如何把最终的步数表示出来，我在此也是研读了其他大佬的代码，思路
就是在结构体中添加步数，把起点能够到达的每个点的步数都赋值给每个点，例如，e2，可以到达所有的点，在遍历的过程中，e2可以到达的所有点所需要的步数都标记在对应点的step中，很巧妙。
我之后又想了下，每次进入dfs的初始step都初始化为0了，到下一个样例就会把之前的step覆盖掉。最后有一个小点：多组样例测试，输入第一个样例后，后面的输不进去，用getchar（）读取缓存。
下面附上我的代码：

1. #include <iostream>  
2. #include <bits/stdc++.h>  
3. #include <queue>  
4. using namespace std;  
5. int mp[15][15]={0};  
6. int dr[8]={-1,-2,-2,-1,1,2,2,1};  
7. int dc[8]={-2,-1,1,2,2,1,-1,-2};  
8. struct point{  
9.     int x;  
10.     int y;  
11.     int step;  
12. };  
13. int ans=0;  
14. point st,ov;  
15. void bfs(point st){  
16.     queue<point>q;  
17.     q.push(st);  
18.     st.step=0;  
19.     mp[st.x][st.y]=1;  
20.     while(!q.empty()){  
21.         point p=q.front();  
22.         q.pop();  
23.         if(p.x==ov.x&&p.y==ov.y)ans=p.step;  
24.         for(int i=0;i<8;i++){  
25.             point np;  
26.             np.x=p.x+dr[i];  
27.             np.y=p.y+dc[i];  
28.             if(np.x>=1&&np.x<=8&&np.y>=1&&  
29.             np.y<=8&&mp[np.x][np.y]==0)  
30.             {  
31.             np.step=p.step+1;  
32.             mp[np.x][np.y]=1;  
33.             q.push(np);   
34.             }  
35.         }  
36.     }  
37. }  
38. int main()  
39. {  
40.     char a,c;  
41.     int b,d;  
42.     while(~scanf("%c%d",&a,&b)){  
43.         memset(mp,0,sizeof(mp));  
44.         ans=0;  
45.         cin>>c>>d;  
46.         st.x=int(a-96);  
47.         st.y=b;  
48.         ov.x=int(c-96);  
49.         ov.y=d;  
50.         bfs(st);  
51.         printf("To get from %c%d to %c%d takes %d knight moves.\n",a,b,c,d,ans);  
52.         getchar();  
53.     }  
54.       
55.     return 0;  
56.  }