当前位置: 首页 > 工具软件 > knight > 使用案例 >

hdu 1372 Knight Moves 解题报告

公孙盛
2023-12-01

题目链接: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 }

 

 

转载于:https://www.cnblogs.com/windysai/archive/2013/05/01/3053893.html

 类似资料: