hdu 1372 Knight Moves 解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1372

        题目的意思是，在一个棋盘里，给出两点a和b，计算a到b的最小步数。玩过象棋的人应该都知道，“马”是走“日”的，这里的走法就是按“马”的走法来走。假设给出的点是（0，0），它下一步只能有8个选择，也就是（1， 2），（1，-2），（-1，2），（-1，-2），（2，1），（2，-1），（-2，1），（-2，-1）。

       这里还有两点要注意：1、输入的字符a-h要化成整型，以便在棋盘里构图。2、最终，每一个knight[i][j]保存的都是最少的步数，否则会递归地找到最少的move数

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int knight[8][8];
 5 int x[] = {1, 1, -1, -1, 2, 2, -2, -2};   //存储8个方向的点，每次用的时候x，y要同步，因为坐标点是由x、y组成的。                                         
 6 int y[] = {2, -2, 2, -2, 1, -1, 1, -1};
 7 
 8 void dfs(int i, int j, int move)
 9 {
10     if (i < 0 || j < 0 || i > 7 || j > 7 || move >= knight[i][j]) //越界或统计的步数不小于knight[i][j]存储的步数则返回，说明knight[i][j]存储的步数不是最少的，继续递归找
11         return;
12     int k;
13     knight[i][j] = move;        //保存当前的move，但有可能不是最优的move 
14     for (k = 0; k < 8; k++)
15     {
16         dfs(i+x[k], j+y[k], move+1); //递归直到每一个knight[i][j]存储的步数最少，move作为计数器每次调用要+1
17     }
18 }
19 
20 int main()
21 {
22     char a[5], b[5];
23     while (scanf("%s%s", a, b) != EOF)
24     {
25         memset(knight, 100, sizeof(knight));  //对knight的每个点赋予足够大的步数
26         dfs(a[1]-'1', a[0]-'a', 0);       //字母代表列，数字代表行，都要化成整型（dfs的形参是整型）
27         printf("To get from %s to %s takes %d knight moves.\n", a, b, knight[b[1]-'1'][b[0]-'a']); //输出的是到b点的最少步数
28     }
29     return 0;
30 }