智能驾驶 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

有一辆汽车需要从 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

输出：
70

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

示例2

输入：
4,4
10,30,30,20
30,30,-1,10
0,20,20,40
10,-1,30,40

输出：
70

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

示例3

输入：
4,5
10,0,30,-1,10
30,0,20,0,20
10,0,10,0,30
10,-1,30,0,10

输出：
60

说明：
行走的路线为：下 -> 下 -> 下 -> 右 -> 右 -> 上 -> 上 -> 上 -> 右 -> 右 -> 下 -> 下 -> 下

示例4

输入：
4,4
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40

输出：
-1

说明：
无论如何都无法到达终点

题解

这道题属于图的最短路径问题，可以使用 动态规划 + BFS 算法解决。以下是解题思路：

1. 首先，我们需要建立一个二维数组 dp，其中 dp[x][y] 表示从终点到达 (x, y) 的最小油耗。
2. 从终点开始进行广度优先搜索（BFS），将节点加入到优先队列中，并根据消耗的油量进行排序。
3. 在每一步搜索中，我们考虑当前节点的四个邻居节点，如果邻居节点是合法的（不超出边界且不是障碍物），则计算到达邻居节点的油耗。
4. 如果邻居节点是加油站，则油耗为0；否则，油耗为当前节点油耗加上到达邻居节点的耗油量。
5. 如果到达邻居节点的油耗小于其当前记录的油耗，更新 dp 数组，并将该节点加入到优先队列中。

最终，我们只需检查起点 (0, 0) 的最小油耗是否不超过 100，如果超过则返回 -1，否则返回最小油耗。

代码中使用了优先队列来存储待探索的节点，以及一个二维数组 dp 来记录每个节点的最小油耗。

在每一步搜索中，我们从优先队列中取出一个节点进行探索，并更新 dp 数组。

Java

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] sizes = scanner.nextLine().split(",");
        // 读入行和列
        int m = Integer.parseInt(sizes[0]);
        int n = Integer.parseInt(sizes[1]);
		
        // 读入矩阵数据
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            String[] row = scanner.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(row[j]);
            }
        }

        // dp[x][y] 表示从右下角（终点）到达 （x, y）所需要的最小油耗
        int[][] dp = new int[m][n];
        // 初始化 dp 每个元素为 Integer.MAX_VALUE 表示不可达
        Arrays.stream(dp).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));

        // 小顶堆
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // 从终点出发
        heap.offer(new int[]{grid[m - 1][n - 1], m - 1, n - 1});
        dp[m - 1][n - 1] = grid[m - 1][n - 1];

        while (!heap.isEmpty()) {
            int[] node = heap.poll();
            int cost = node[0], x = node[1], y = node[2];
            int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};