2025 A卷 200分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《智能驾驶》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C

GO

---

题目名称：智能驾驶

---

• 知识点：动态规划、贪心算法、图搜索（BFS/DFS）
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

一辆汽车需要从 ( m \times n ) 的地图左上角（起点）行驶到右下角（终点）。每个格子有以下属性：

• -1：加油站，可加满油（油箱容量最大为100）。
• 0：障碍物，无法通过。
• 正整数：通过该格子需消耗的油量。

规则：

1. 汽车可上下左右移动。
2. 初始油量需确保能到达终点，计算最少初始油量。若无法到达，返回-1。
3. 油箱初始为空，若起点为加油站则初始油量为100。

输入：

• 首行两个整数 ( m ) 和 ( n )，表示地图行数和列数。
• 接下来 ( m ) 行，每行 ( n ) 个整数，表示地图数据。

输出：

• 最少初始油量或-1。

示例：
输入：

2 2  
10 20  
30 40  

输出：

70  

解释：路径为右→下，初始油量需 ≥ 10（起点） + 30（下一步） = 40，但实际需覆盖路径最大累计消耗（10+20+40=70）。

---

Java

问题分析

汽车需要从地图左上角移动到右下角，每个格子可能有不同的油量消耗或加油站。油箱容量最大为100，初始油量为空。若起点是加油站，初始油量为100。要求找到能到达终点的最小初始油量，若无法到达返回-1。

解题思路

1. 动态规划与优先队列：使用Dijkstra算法，优先扩展当前最大油量消耗最小的路径。
2. 状态定义：每个状态包括当前位置、当前区段累计油量、路径最大油量消耗。
3. 加油站处理：到达加油站时，油量加满，当前区段累计油量重置为0。
4. 障碍物处理：遇到障碍物直接跳过。

代码实现

import java.util.*;class State implements Comparable<State> {int i, j;int currentSegment;int maxSoFar;public State(int i, int j, int currentSegment, int maxSoFar) {this.i = i;this.j = j;this.currentSegment = currentSegment;this.maxSoFar = maxSoFar;}@Overridepublic int compareTo(State other) {return Integer.compare(this.maxSoFar, other.maxSoFar);}
}public class Main {private static String getKey(int i, int j, int segment) {return i + "," + j + "," + segment;}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();}}// 起点是障碍物if (grid[0][0] == 0) {System.out.println(-1);return;}PriorityQueue<State> pq = new PriorityQueue<>();Map<String, Integer> dist = new HashMap<>();// 初始化起点if (grid[0][0] == -1) {pq.offer(new State(0, 0, 0, 0));dist.put(getKey(0, 0, 0), 0);} else {int initialCost = grid[0][0];pq.offer(new State(0, 0, initialCost, initialCost));dist.put(getKey(0, 0, initialCost), initialCost);}int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};while (!pq.isEmpty()) {State state = pq.poll();int i = state.i;int j = state.j;int currentSegment = state.currentSegment;int maxSoFar = state.maxSoFar;// 到达终点if (i == m - 1 && j == n - 1) {System.out.println(maxSoFar);return;}String currentKey = getKey(i, j, currentSegment);if (dist.getOrDefault(currentKey, Integer.MAX_VALUE) < maxSoFar) {continue;}for (int[] dir : dirs) {int ni = i + dir[0];int nj = j + dir[1];if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;int cellValue = grid[ni][nj];if (cellValue == 0) continue;int cost = cellValue == -1 ? 0 : cellValue;int newSegment = currentSegment + cost;boolean isGasStation = cellValue == -1;int newMax = Math.max(maxSoFar, newSegment);// 处理加油站if (isGasStation) {if (newSegment > 100) continue;newSegment = 0; // 加满油，新区段从0开始} else {// 来自加油站或起点是加油站，新区段不能超过100if (currentSegment == 0 && newSegment > 100) {continue;}}int newSegmentAfter = isGasStation ? 0 : newSegment;State newState = new State(ni, nj, newSegmentAfter, newMax);String newKey = getKey(ni, nj, newSegmentAfter);if (!dist.containsKey(newKey) || newMax < dist.getOrDefault(newKey, Integer.MAX_VALUE)) {dist.put(newKey, newMax);pq.offer(newState);}}}System.out.println(-1);}
}

代码详解

1. State类：存储当前位置、当前区段累计油量、路径最大油量消耗，并实现优先队列比较接口。
2. 输入处理：读取地图数据，处理起点障碍物情况。
3. 优先队列初始化：根据起点是否为加油站设置初始状态。
4. 状态扩展：遍历四个方向，计算新位置的油量消耗，处理加油站逻辑，更新状态并加入优先队列。
5. 终点检测：到达终点时输出结果。

示例测试

示例1输入：

2 2
10 20
30 40

输出：70

示例2输入：

3 3
-1 20 0
30 0 40
50 60 70

输出：100（路径包含加油站，最大区段消耗为30+50=80，但需加满油）

示例3输入：

2 2
0 10
20 30

输出：-1（起点障碍物）

综合分析

• 时间复杂度：使用优先队列处理状态，最坏情况O(N log N)，适用于小规模地图。
• 空间复杂度：存储状态信息，O(MNC)，C为区段油量可能值。
• 正确性：通过Dijkstra算法保证找到最优路径，处理加油站和障碍物逻辑。
• 适用性：适用于各种地图配置，正确处理油量限制和加油站逻辑。

---

python

问题分析

汽车需要从地图左上角移动到右下角，每个格子可能有不同的油量消耗或加油站。油箱容量最大为100，初始油量为空。若起点是加油站，初始油量为100。要求找到能到达终点的最小初始油量，若无法到达返回-1。

解题思路

1. 优先队列（Dijkstra算法）：每次扩展当前最大油量消耗最小的路径。
2. 状态定义：每个状态包括位置、当前区段累计油量、路径最大油量消耗。
3. 加油站处理：到达加油站时，油量加满，当前区段累计油量重置为0。
4. 障碍物处理：遇到障碍物直接跳过。

代码实现

import heapqdef min_initial_fuel(grid):m = len(grid)if m == 0:return -1n = len(grid[0])if grid[0][0] == 0:return -1  # 起点是障碍物start_val = grid[0][0]# 初始化起点状态if start_val == -1:initial_segment = 0initial_max = 0else:if start_val > 100:return -1  # 初始油量不足initial_segment = start_valinitial_max = start_valheap = []heapq.heappush(heap, (initial_max, 0, 0, initial_segment))visited = {}visited_key = (0, 0, initial_segment)visited[visited_key] = initial_maxdirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]while