注意事项

本文包括社招题库中的较困难题目，如华为OD中分值为200的题目

回溯

勇攀数字高峰

题目描述

你在给定的数字地形图中寻找登山路径，数字代表当前位置的海拔高度，要求从最低海拔出发，不断攀登，最终到达最高山峰，你需要寻找所有满足条件的登山路径。地图 保证最低海拔和最高山峰只有一个。

路径条件

  • 登山规则：路径海拔必须严格递增
  • 移动限制：可以上下左右四个方向 移动
  • 路径限制：路径必须从最低海拔开始，到最高海拔结束
  • 访问限制：每个地点只能走一次
  • 高度差限制：每一个攀登高度必须大于 0，小于等于指定值。

输入描述

输入一个二维数组 表示的海拔图，维度 n * m （2 <= n, m <= 10）
输入一个整数，参数表示单步最大允许的高度差

输出描述

输出满足条件的登山路径的数量

用例1

1
2
3
4
5
6
7
8
9
输入：
4 4 5
7 6 4 5
9 5 1 1
2 4 1 4
1 3 2 0

输出：
2
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package b_hard;

import java.util.*;

public class b01_climbing_the_digital_summit {


    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static boolean[][] visited = new boolean[15][15];
    static int sx, sy, ex, ey;

    // 递归回溯
    public static int dfs(int x, int y, int n, int m, int k, int[][] grid) {
        // 到达终点
        if (x == ex && y == ey) {
            return 1;
        }

        visited[x][y] = true;
        int res = 0;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 越界
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            // 重复
            if (visited[nx][ny]) continue;

            int diff = grid[nx][ny] - grid[x][y];

            if (diff > 0 && diff <= k) {
                res += dfs(nx, ny, n, m, k, grid);
            }
        }

        visited[x][y] = false; // 回溯
        return res;
    }

    public static int cal(int n, int m, int k, int[][] grid) {

        // 找到终点/起点坐标
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] < minVal) {
                    minVal = grid[i][j];
                    sx = i;
                    sy = j;
                }
                if (grid[i][j] > maxVal) {
                    maxVal = grid[i][j];
                    ex = i;
                    ey = j;
                }
            }
        }

        return dfs(sx, sy, n, m, k, grid);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        int[][] grid = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        System.out.println(cal(n, m, k, grid));
    }
}

广度优先搜索（BFS）

直捣黄龙

题目描述
小王在玩一款叫做直捣黄龙的小游戏，在该游戏中他需要从入口位置进入敌营，绕过哨兵的层层封锁，达到敌军司令部实施斩首行动。
敌军阵营是一个 n*n 的矩阵，入口在坐标 (0, n/2)，敌军司令部在坐标 (n-1, n/2)，每个哨兵警戒以自己为中心的9宫格，一旦被哨兵发现则行动失败。同时穿越敌营耗时越长，被发现的概率越高，因此小王需要寻找到可以绕过警戒到达敌军司令部的最短路径。请你设计一个小程序，帮助小王统计这样的路径有多少条，以及路径长度。

规则说明：

  1. 其中 n 为大于 1 的奇数且取值小于 30，坐标 x，y 取值均从 0 开始，敌营左下角定义为 (0,0)，右上角定义为 (n-1,n-1)
  2. 敌营入口在坐标 (0, n/2)，敌军司令部在坐标 (n-1, n/2)。
  3. 游戏角色的行动方向只包含上、下、左、右四个方向，即一次行动 x、y坐标不可同时变化。
  4. 在没有满足题目要求的可达路径时，需要返回0 0。

输入描述
参数 1，敌军阵营的边长 n。
参数 2，哨兵位置列表 Point{x,y}:x 未行坐标，y 为列坐标。x和y以逗号分割，不同坐标以空格分割

输出描述
输出两个成员空格分割，第一个成员为最短路径条数，第二个成员为最短路径长度。

用例1

1
2
3
4
5
6
7
8
9
10
11
12
输入：
5
2,2

输出：
2 9

说明：
两条最短路径，S 表示哨兵位置，A 表示起点，E 表示终点
路径1:[(0,2),(0,1),(0,0),(1,0),(2,0),(3,0),(4,0),(4,1),(4,2)]
路径2：[(0,2),(0,3),(0,4),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2)]
因此返回为2 9

用例2

1
2
3
4
5
6
7
8
9
输入：
3
1,1

输出：
0 0

说明：
无路径场景，S 表示哨兵位置，A 表示起点，E 表示终点，哨兵警戒了全图
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package b_hard;

import java.util.*;

// 直捣黄龙
// https://blog.csdn.net/qq_45776114/article/details/159973152
class Point {
    int x, y;

    Point(int xx, int yy) {
        x = xx;
        y = yy;
    }
}

public class b02_storm_the_enemy_den {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine(); // 吃掉换行
        String line = sc.nextLine();
        List<Point> points = new ArrayList<>();
        for (String s : line.split(" ")) {
            String[] rowCol = s.split(",");
            points.add(new Point(Integer.parseInt(rowCol[0]), Integer.parseInt(rowCol[1])));
        }

        int[] res = calShortestPath(n, points);
        System.out.println(res[0] + " " + res[1]);
    }

    static int[] calShortestPath(int n, List<Point> points) {
        int[][] grid = new int[n][n];
        // 标记不可达位置
        for (Point point : points) {
            int x = point.x;
            int y = point.y;
            for (int i = x - 1; i <= x + 1; i++) {
                for (int j = y - 1; j <= y + 1; j++) {
                    if (i < 0 || i >= n || j < 0 || j >= n) continue;
                    grid[i][j] = -1;
                }
            }
        }

        // 上下左右的另一种写法
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int sx = 0, sy = n / 2;
        int ex = n - 1, ey = n / 2;

        // 特殊情况判断
        if (grid[sx][sy] == -1 || grid[ex][ey] == -1) return new int[]{0, 0};

        // dist 记录节点数，-1 表示未访问
        // 记录从起点到每个格子的最短距离（经过的格子数）
        int[][] dist = new int[n][n];
        // distNum 最少节点数到达次数方案数
        int[][] distNum = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, -1);

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sx, sy});
        dist[sx][sy] = 1;
        distNum[sx][sy] = 1;

        while (!q.isEmpty()) {
            // 一个循环取出一个
            int[] p = q.poll();
            int x = p[0], y = p[1];
            for (int[] d : dirs) {
                int nx = x + d[0];
                int ny = y + d[1];
                // 越界或被监控
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == -1) continue;

                // 初次访问
                if (dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    // 数量相同
                    distNum[nx][ny] = distNum[x][y];
                    // 根据不同方向每次都加入队列
                    q.offer(new int[]{nx, ny});
                } else if (dist[x][y] + 1 == dist[nx][ny]) {
                    distNum[nx][ny] += distNum[x][y];
                }
            }
        }

        // 不可达
        if (dist[ex][ey] == -1) return new int[]{0, 0};
        return new int[]{distNum[ex][ey], dist[ex][ey]};
    }
}

过程演示