智能驾驶 - 华为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 算法解决。以下是解题思路：
- 首先，我们需要建立一个二维数组
dp，其中dp[x][y]表示从终点到达(x, y)的最小油耗。- 从终点开始进行广度优先搜索（BFS），将节点加入到优先队列中，并根据消耗的油量进行排序。
- 在每一步搜索中，我们考虑当前节点的四个邻居节点，如果邻居节点是合法的（不超出边界且不是障碍物），则计算到达邻居节点的油耗。
- 如果邻居节点是加油站，则油耗为0；否则，油耗为当前节点油耗加上到达邻居节点的耗油量。
- 如果到达邻居节点的油耗小于其当前记录的油耗，更新
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}};
for (int[] dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 0) { // 这个地区是障碍物，汽车不能通过
continue;
}
// 到达加油站时可以加满油，因此油耗需要是 0
// 非加油站则需要累积油耗需要
int ncost = (grid[nx][ny] == -1) ? 0 : cost + grid[nx][ny];
// 到达地区（nx, ny）所需油耗不超过汽车的油箱容量则可以到达
// 到达地区（nx, ny）所需油耗更小则尝试继续探索
if (ncost <= 100 && ncost < dp[nx][ny]) {
dp[nx][ny] = ncost;
heap.offer(new int[]{ncost, nx, ny});
}
}
}
}
if (dp[0][0] > 100) {
System.out.println(-1);
} else {
System.out.println(dp[0][0]);
}
}
}
Python
import heapq
from math import inf
m, n = map(int, input().split(','))
grid = [list(map(int, input().split(','))) for _ in range(m)]
# dp[x][y] 表示从右下角（终点）到达 （x, y）所需要的最小油耗
dp = [[inf]*n for _ in range(m)]
hp = []
heapq.heappush(hp, (grid[m-1][n-1], m-1, n-1))
dp[m-1][n-1] = grid[m-1][n-1]
while hp:
cost, x, y = heapq.heappop(hp)
for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]: # 四个方向进行探索
nx, ny = x+dx, y+dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == 0: # 这个地区是障碍物，汽车不能通过
continue
if grid[nx][ny] == -1: # 这个地区加油站，可以加满油
ncost = 0
else:
ncost = cost + grid[nx][ny]
# 到达地区（nx, ny）所需油耗不超过汽车的油箱容量则可以到达
# 到达地区（nx, ny）所需油耗更小则尝试继续探索
if ncost <= 100 and ncost < dp[nx][ny]:
dp[nx][ny] = ncost
heapq.heappush(hp, (ncost, nx, ny))
if dp[0][0] > 100:
print(-1)
else:
print(dp[0][0])
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m, n;
// 读入行和列
cin >> m;
if (cin.peek() == ',') cin.ignore();
cin >> n;
// 读入矩阵数据
vector<vector<int>> grid(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> grid[i][j];
if (cin.peek() == ',') cin.ignore();
}
}
// dp[x][y] 表示从右下角（终点）到达 （x, y）所需要的最小油耗, dp 每个元素为 Integer.MAX_VALUE 表示不可达
vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
// 小顶堆
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
// 从终点出发
pq.push({grid[m - 1][n - 1], m - 1, n - 1});
dp[m - 1][n - 1] = grid[m - 1][n - 1];
while (!pq.empty()) {
vector<int> node = pq.top(); pq.pop();
int cost = node[0], x = node[1], y = node[2];
vector<vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
for (const auto& dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 0) { // 这个地区是障碍物，汽车不能通过
continue;
}
// 到达加油站时可以加满油，因此油耗需要是 0
// 非加油站则需要累积油耗需要
int ncost = (grid[nx][ny] == -1) ? 0 : cost + grid[nx][ny];
// 到达地区（nx, ny）所需油耗不超过汽车的油箱容量则可以到达
// 到达地区（nx, ny）所需油耗更小则尝试继续探索
if (ncost <= 100 && ncost < dp[nx][ny]) {
dp[nx][ny] = ncost;
pq.push({ncost, nx, ny});
}
}
}
}
if (dp[0][0] > 100) {
cout << -1 << endl;
} else {
cout << dp[0][0] << endl;
}
return 0;
}
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#面经##秋招##春招##校招##华为#