noj -> 跳马

2021-10-24

00 题目

描述:

在国际象棋中,马的走法与中车象棋类似,即俗话说的“马走日”,下图所示即国际象棋中马(K)在一步能到达的格子(其中黑色的格子是能到达的位置)。

 

 

现有一200*200大小的国际象棋棋盘,棋盘中仅有一个马,给定马的当前位置(S)和目标位置(T),求出马最少需要多少跳才能从当前位置到达目标位置。

输入:

本题包含多个测例。输入数据的第一行有一个整数N(1<=N<=1000),表示测例的个数,接下来的每一行有四个以空格分隔的整数,分别表示马当前位置及目标位置的横、纵坐标C(x,y)和G(x,y)。坐标由1开始。

输出:

对于每个测例,在单独的一行内输出一个整数,即马从当前位置跳到目标位置最少的跳数。

输入样例:

2
1 1 2 1
1 5 5 1

输出样例:

3
4

01 思路

01-1 类型

很明显求解“马从当前位置跳到目标位置最少的跳数”,且在一个类迷宫的Map里,考虑使用广度优先搜索,每次将可以跳到的的且没到过的位置入队,判断是否达到终点。

01-2 算法

由于对于多组起点终点进行广搜,所以在上位函数应当是个循环,循环控制变量应该是组数,下面是对于每一组进行广搜的步骤:

  • 初始化地图

  • 进行队列操作的准备

    • 将输入起点转换为队列类型Node

    • 创建队列并作初始化操作map值为0,将起点入队

  • 队列非空,执行下列操作

    • 取出队列首节点,进行判断

      • 若为终点,return当前map数组里的值即为路径长度

      • 若非终点,则遍历jump数组的跳法(此题中一共8个)产生子节点NextNode,将符合条件的入队

    • 循环这个操作,直到队列空

02 代码

 1 //跳马
 2 #include<iostream>
 3 #include<queue>
 4  5 using namespace std;
 6  7 typedef struct{
 8     int row;
 9     int col;
10 }Node;
11 12 int n;
13 int inx,iny;
14 //出发点
15 int outx,outy;
16 //终点
17 int map[200][200];
18 //棋盘二维数组
19 int jump[8][2] = {{1,2},{2,1},{1,-2},{2,-1},{-1,-2},{-2,-1},{-1,2},{-2,1}};
20 //跳跃步法,遍历这个数组就可以遍历某个点的所有下一位置节点
21 int result[1000];
22 //result是用来记录每一组入口出口的最短路径长度,题目要求1000
23 24 void init();
25 int bfs();
26 void oper_map();
27 void out_result();
28 29 int main(){
30     //广搜组数
31     cin >> n;
32     //init()初始化map,但是这一步需要在每一次广搜前初始化,来实现归零
33     //init();
34     //oper_map//调用bfs填充result
35     oper_map();
36     //cout_result//输出结果
37     out_result();
38     return 0;
39 }
40 void init(){
41     for(int i = 0; i < 200; i++){
42         for(int j = 0; j < 200; j++){
43             map[i][j]=-1;
44         }//初始化这个map
45     }
46 }
47 void oper_map(){
48     for(int i = 0;i < n; i++){
49         cin >> inx >> iny >> outx >> outy ;
50         result[i] = bfs();
51     }
52 }
53 void out_result(){
54     for(int i = 0; i < n; i++){
55         cout << result[i] << endl;
56     }
57 }
58 int bfs(){
59     //每次都需要初始化map
60     init();
61 62     Node node;
63     node.row = inx - 1;
64     node.col = iny - 1;
65 66     queue<Node> q;
67     q.push(node);
68     map[node.row][node.col] = 0;
69 70     while(!q.empty()){
71         Node nowNode = q.front();
72         q.pop();
73         int row = nowNode.row;
74         int col = nowNode.col;
75         if(row == outx - 1 && col == outy - 1){
76             return map[row][col];
77         }
78         else{
79             Node nextNode;
80             for(int i = 0;i < 8; i++){
81                 nextNode.row = row + jump[i][0];
82                 nextNode.col = col + jump[i][1];
83 84                 if(nextNode.row >= 0 && nextNode.row < 200 && nextNode.col >= 0 && nextNode.col < 200 && map[nextNode.row][nextNode.col] == -1){
85                     map[nextNode.row][nextNode.col] = map[row][col] + 1;
86                     q.push(nextNode);
87                 }
88             }
89         }
90     }
91     return -1;
92 }