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

喜欢ヅ旅行 2024-04-25 08:43 90阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][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、说明 ####

行走的路线为：右 -> 下

### 四、解题思路 ###

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

解题思路：

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、输入 ####

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

#### 2、输出 ####

#### 3、说明 ####

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

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

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

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

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/903aeec11a5447548c2e0dc5f547806e.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/649744bc36ca46ceb09b4fdadb9442c2.gif