华为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、输出

3、说明

行走的路线为：右 -> 下

四、解题思路

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

解题思路：

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

五、广度优先搜索

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

BFS 的步骤：

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

六、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) {// 如果起点或终点是障碍物，直接返回-1if (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});}}}}// 如果所有可能的路径都被探索后仍无法到达终点，返回-1return -1;}
}