华为OD机试 - 智能驾驶 - 广度优先搜索（Java 2024 C卷 200分）

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有一辆汽车需要从 m * n 的地图的左上角（起点）开往地图的右下角（终点 ），去往每一个地区都需要消耗一定的油量，加油站可进行加油

请你计算汽车确保从起点到达终点时所需的最少初始油量

说明：

（1）智能汽车可以上下左右四个方向移动;

（2）地图上的数字取值是 0 或 −1 或者正整数;

−1：表示加油站，可以加满油，汽车的油箱容量最大为 100；

0 ：表示这个地区是障碍物，汽车不能通过;

正整数：表示汽车走过这个地区的耗油量

（3）如果汽车无论如何都无法到达终点，则返回 −1

二、输入描述

第一行为两个数字，M , N，表示地图的大小为 M * N ( 0 < M,N ≤ 200 )

后面一个M * N 的矩阵，其中的值是 0 或 −1 或正整数，加油站的总数不超过 200个

三、输出描述

如果汽车无论如何都无法到达终点，则返回-1

如果汽车可以到达终点，则返回最少的初始油量

1、输入

2 2
10 20
30 40

2、输出

70

3、说明

行走的路线为：右 -> 下

四、解题思路

这个问题可以被视为一个图搜索问题，我们需要找到从起点到终点的最佳路径，使得汽车在任意时刻都不耗尽油量。更具体地说，我们希望找到一个路径，使得从起点到终点所需的初始油量最少。

解题思路：

1. 状态表示与搜索：使用广度优先搜索（BFS）来遍历地图。每个状态由 (x, y, fuel) 表示，其中 x 和 y 是汽车的当前位置，fuel 是当前的剩余油量。
2. 维护剩余油量：在搜索过程中，我们需要维护从起点到当前位置所需要的最少初始油量。我们可以使用一个 minFuel[x][y] 数组来记录到达 (x, y) 所需的最小初始油量。
3. 加油站处理：当汽车到达一个加油站（地图值为 -1），油量将被充满至 100。
4. 油量计算：当从一个点移动到另一个点时，需要根据地图上的数值来增减油量。
5. 边界与障碍物处理：如果遇到障碍物（地图值为 0），该方向将不被考虑。同时需要确保汽车在任何时刻的油量都不为负。

五、广度优先搜索

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。这种算法从树的根（或图的某一顶点）开始，访问当前层的所有节点，然后前往下一层级。

BFS 的步骤：

1. 将起始节点放入队列中。
2. 从队列中取出一个节点，并检查它：
   • 如果它是目标节点，搜索结束。
   • 否则，将它所有尚未检查过的相邻节点加入队列中。
3. 重复步骤2，直到队列为空或找到目标节点。
4. 如果队列为空且未找到目标节点，则目标节点不在图中。

六、Java算法源码

public class Test06 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt(); // 读取地图的行数
        int N = scanner.nextInt(); // 读取地图的列数
        int[][] grid = new int[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = scanner.nextInt(); // 填充地图的每个格子
            }
        }
        System.out.println(minInitialFuel(M, N, grid)); // 计算并输出最少的初始油量
    }

    // 函数用于计算从地图的左上角到右下角所需的最少初始油量
    public static int minInitialFuel(int M, int N, int[][] grid) {
        // 如果起点或终点是障碍物，直接返回-1
        if (grid[0][0] == 0 || grid[M-1][N-1] == 0) {
            return -1;
        }

        // 创建一个数组用来存储到达每个点的最小初始油量
        int[][] minFuel = new int[M][N];
        for (int[] row : minFuel) {
            Arrays.fill(row, Integer.MAX_VALUE); // 初始化为极大值
        }
        // 起点的最小初始油量，如果起点是加油站，则为0，否则为格子上的数值
        minFuel[0][0] = grid[0][0] > 0 ? grid[0][0] : 0;

        // 方向数组，表示上下左右四个移动方向
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        // 使用优先队列按照已消耗的油量排序，确保总是先处理需要油量最少的路径
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        pq.offer(new int[] {0, 0, minFuel[0][0]}); // 起始位置入队

        // 广度优先搜索
        while (!pq.isEmpty()) {
            int[] current = pq.poll(); // 取出队列中油耗最少的状态
            int x = current[0];
            int y = current[1];
            int fuelUsed = current[2];

            // 到达终点，返回所需的最小初始油量
            if (x == M - 1 && y == N - 1) {
                return fuelUsed;
            }

            // 探索四个可能的移动方向
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i]; // 新的行坐标
                int ny = y + dy[i]; // 新的列坐标

                // 确保新坐标在地图范围内，并且不是障碍物
                if (nx >= 0 && nx < M && ny >= 0 && ny < N && grid[nx][ny] != 0) {
                    // 计算到新位置的所需油量
                    int requiredFuel = fuelUsed + (grid[nx][ny] > 0 ? grid[nx][ny] : 0);
                    // 如果到达加油站，则可以将油量补满至100或保持原油量中的较小值
                    if (grid[nx][ny] == -1) {
                        requiredFuel = Math.min(fuelUsed, 100);
                    }
                    // 如果找到更少油耗的路径到达(nx, ny)，则更新minFuel并将状态入队
                    if (requiredFuel < minFuel[nx][ny]) {
                        minFuel[nx][ny] = requiredFuel;
                        pq.offer(new int[] {nx, ny, requiredFuel});
                    }
                }
            }
        }

        // 如果所有可能的路径都被探索后仍无法到达终点，返回-1
        return -1;
    }
}
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

七、效果展示

1、输入

4 4
10 30 30 20
30 30 -1 10
0 20 20 40
10 -1 30 40

2、输出

70

3、说明

行走的路线为：右 -> 右 -> 下 -> 下 -> 下 -> 右

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷+C卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。