华为机试2022年3月30号_给定一个m * n的整教短阵作为地图,矩阵数值为地形高度 中庸行者选择地图中的任意

华为武长地区2022年3月30号机试第二道编程题代码c++实现

题目描述：
给定一个m*n数组，起点start和终点end坐标以及边界坐标，并设置障碍点数组obstacle，障碍点给定方式为，题目输入障碍点个数k和坐标数组，要求求从起点到终点最短路径及最短路径个数)
比如输入：

5 5//m*n数组
0 1//起点start
3 3//终点end
1//障碍点个数k
2 2//障碍点数组
1
2
3
4
5

输出：

4 5//最短路径个数和长度
1

找路径问题：DFS+回溯
由于要找最短，所以只能向右边或者下边前进，前进的过程中需要设置一个已访问过的数组visited作为标识，且防止数组下标越界，同时要避开障碍点，避开的方式就是遇到障碍点就返回，找到一条路径之后，也即到达终点，对当前路径长度和已有最短路径长度进行比较，更新最短长度路径，并将路径个数+1，之后进行回溯，将访问过的坐标重新置为0即可。
话不多说直接上代码

 void DFS(int m,int n,vector<int>& end,vector<vector<int>>& obstacle,int i, int j,int k,vector<vector<int>>& visited,int len,int& minlen,int& count) {
     //判断当前位置是否超过边界
     if (i < 0 || j < 0 || i >= m || j >= n) {
         return;
     }
     //如果当前位置到达终点，对已经累加好的路径长度和最小长度比较，若小于则将其赋值给最小长度，同时将长度个数加1
     if (i == end[0] && j == end[1]) {
         if (len < minlen) {
             minlen = len;
         }
         count++;
         return;
     }
     //判断当前位置是否是障碍
     for (int c = 0; c < k; c++) {
         if (i == obstacle[c][0] && j == obstacle[c][1])
             return;
     }
     //判断当前位置是否已经访问过
    if (visited[i][j] == 1) {
        return;
    }
    //若没有访问过就进行下一个位置（向下或者向右）进行访问，并将visited[i][j]置为1，表示已经访问
     visited[i][j] = 1;
     DFS(m, n, end, obstacle, i + 1, j, k,visited, len+1, minlen, count);
     DFS(m, n, end, obstacle, i, j + 1, k,visited, len+1, minlen, count);
     //回溯将访问过的位置重新置为0，为后续新的路径做准备
     visited[i][j] = 0;
     
 }
 vector<int> minLength(int m,int n, vector<int>& start, vector<int>& end, int k, vector<vector<int>>& obstacle) {
     //定义len表示当前路径长度，minlen表示最小长度（初始化为最大值），count表示最短长度路径个数
     int len = 0, count = 0, minlen = INT_MAX;
     //访问标识数组
     vector<vector<int>>visited(n, vector<int>(m, 0));
     //进行深度优先遍历
     DFS(m, n, end, obstacle, start[0], start[1],2, visited,len, minlen, count);
     //将结果加入到结果数组中
     vector<int>ans;
     ans.push_back(count);
     ans.push_back(minlen);
     return ans;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43