1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stack>
 6 #include <queue>
 7 using namespace std;
 8 int f[10][10];
 9 int a[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; //“马走日”所能够到达的八个位置 
10 int change(char ch)  //将a--h转换成对应的1--8 
11 {
12     if (ch == ‘a‘)
13         return 1;
14     if (ch == ‘b‘)
15         return 2;
16     if (ch == ‘c‘)
17         return 3;
18     if (ch == ‘d‘)
19         return 4;
20     if (ch == ‘e‘)
21         return 5;
22     if (ch == ‘f‘)
23         return 6;
24     if (ch == ‘g‘)
25         return 7;
26     if (ch == ‘h‘)
27         return 8;
28 }
29 void bfs(int x,int y,int aa,int b)  //广搜 
30 {
31     memset(f,0,sizeof(f));
32     queue <int > q;  //也可以定义成一个结构体，这样可以少定义一个队列 
33     queue <int > p;
34     q.push(x);
35     p.push(y);
36     f[q.front()][p.front()] = 1;
37     if (x == aa && y == b)  //如果第一个位置和第二个位置相同直接结束 
38         return ;
39     while (!q.empty())  
40     {
41         int x1 = q.front();
42         int y1 = p.front();
43         int ans = f[x1][y1];
44         for (int i = 0; i < 8; i ++)  //以此判断八个位置 
45         {
46             int x2 = x1 + a[i][0];
47             int y2 = y1 + a[i][1];
48             if (x2>0&&x2<=8&&y2>0&&y2<=8&&f[x2][y2]==0)  //注意边界、已经找过的位置不用再找 
49             {
50                 q.push(x2);
51                 p.push(y2);
52                 f[x2][y2] = ans+1;
53             }
54             if (x2 == aa && y2 == b)
55                 return ;
56         }
57         q.pop();
58         p.pop();
59     }
60 }
61 int main ()
62 {
63     char ch1[5],ch2[5];
64     int x,y,a,b;
65     while (scanf("%s",ch1)!=EOF)
66     {
67         scanf("%s",ch2);
68         x = ch1[0]-‘a‘+1;
69         a = ch2[0]-‘a‘+1;
70         y = ch1[1] - ‘0‘;
71         b = ch2[1] - ‘0‘;
72         bfs(x,y,a,b);
73         printf("To get from %s to %s takes %d knight moves.\n",ch1,ch2,f[a][b]-1);
74     }
75     return 0;
76 }