当前位置： 首页 > ds >正文

华为OD机试真题——智能驾驶（2025A卷：200分）Java/python/JavaScript/C/C++/GO最佳实现

ds 2025/5/5 8:10:27

在这里插入图片描述

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 heap:current_max, i, j, current_segment = heapq.heappop(heap)if i == m - 1 and j == n - 1:return current_max  # 到达终点，返回当前最大消耗# 如果当前状态已被更优的状态覆盖，跳过if visited.get((i, j, current_segment), float('inf')) < current_max:continuefor di, dj in dirs:ni, nj = i + di, j + djif 0 <= ni < m and 0 <= nj < n:cell_val = grid[ni][nj]if cell_val == 0:continue  # 障碍物，跳过# 计算当前格子的油耗cost = cell_val if cell_val != -1 else 0new_segment = current_segment + costif new_segment > 100:continue  # 油量超过油箱容量，无法移动new_max = max(current_max, new_segment)# 判断是否为加油站，重置区段累计if cell_val == -1:new_segment_after = 0else:new_segment_after = new_segmentnew_key = (ni, nj, new_segment_after)# 更新最优状态if new_max < visited.get(new_key, float('inf')):visited[new_key] = new_maxheapq.heappush(heap, (new_max, ni, nj, new_segment_after))return -1  # 无法到达终点# 示例测试
example1 = [[10, 20],[30, 40]
]
print(min_initial_fuel(example1))  # 输出: 70example2 = [[-1, 20, 0],[30, 0, 40],[50, 60, 70]
]
print(min_initial_fuel(example2))  # 输出: 100example3 = [[0, 10],[20, 30]
]
print(min_initial_fuel(example3))  # 输出: -1

代码详解

  1. 输入处理：检查地图有效性，处理起点障碍物。
  2. 初始化起点状态：根据起点是否为加油站设置初始油量。
  3. 优先队列初始化：使用堆存储当前最优状态。
  4. 状态扩展：遍历四个方向，计算新位置油量消耗，处理加油站和障碍物。
  5. 终点检测：到达终点返回当前最大消耗。

示例测试

  1. 示例1：路径为右→下，总消耗70。
  2. 示例2：路径包含加油站，初始油量100。
  3. 示例3：起点障碍物，无法到达。

综合分析

  1. 时间复杂度：最坏情况O(MN100 log(MN100))，适用于小规模地图。
  2. 空间复杂度：存储状态信息，O(MN100)。
  3. 正确性：严格处理加油站、障碍物，确保路径区段油量不超限。
  4. 适用性：适用于各类地图配置，高效找到最优解。

JavaScript

问题分析

汽车需要从地图左上角移动到右下角，每个格子可能有油量消耗、加油站或障碍物。要求找到到达终点的最小初始油量。

解题思路

  1. Dijkstra算法：使用优先队列扩展当前最优路径。
  2. 状态管理：记录当前位置、当前区段累计油耗和路径最大油耗。
  3. 加油站处理：到达加油站时加满油（重置区段累计为0）。
  4. 障碍物处理：跳过无法通行的格子（值为0）。

代码实现

class PriorityQueue {constructor() {this.queue = [];}// 插入元素（按maxSoFar升序排列）enqueue(element) {let inserted = false;for (let i = 0; i < this.queue.length; i++) {if (element.maxSoFar < this.queue[i].maxSoFar) {this.queue.splice(i, 0, element);inserted = true;break;}}if (!inserted) this.queue.push(element);}// 取出队首元素dequeue() {return this.queue.shift();}isEmpty() {return this.queue.length === 0;}
}function minInitialFuel(grid) {const m = grid.length;if (m === 0) return -1;const n = grid[0].length;if (grid[0][0] === 0) return -1; // 起点是障碍物const pq = new PriorityQueue();const visited = new Map();// 初始化起点状态const startVal = grid[0][0];if (startVal === -1) {pq.enqueue({ i: 0, j: 0, currentSegment: 0, maxSoFar: 0 });visited.set(`0,0,0`, 0);} else {const initialCost = startVal;pq.enqueue({ i: 0, j: 0, currentSegment: initialCost, maxSoFar: initialCost });visited.set(`0,0,${initialCost}`, initialCost);}const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];while (!pq.isEmpty()) {const { i, j, currentSegment, maxSoFar } = pq.dequeue();// 到达终点if (i === m - 1 && j === n - 1) return maxSoFar;// 跳过非最优路径const key = `${i},${j},${currentSegment}`;if (visited.get(key) < maxSoFar) continue;for (const [di, dj] of dirs) {const ni = i + di;const nj = j + dj;if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;const cellVal = grid[ni][nj];if (cellVal === 0) continue; // 障碍物跳过// 计算油耗const cost = cellVal === -1 ? 0 : cellVal;let newSegment = currentSegment + cost;const isGasStation = cellVal === -1;// 检查油量是否溢出if (newSegment > 100) continue;// 处理加油站let newSegmentAfter = newSegment;if (isGasStation) {newSegmentAfter = 0; // 加满油}// 更新最大消耗const newMax = Math.max(maxSoFar, newSegment);const newKey = `${ni},${nj},${newSegmentAfter}`;if (!visited.has(newKey) || newMax < visited.get(newKey)) {visited.set(newKey, newMax);pq.enqueue({i: ni,j: nj,currentSegment: newSegmentAfter,maxSoFar: newMax});}}}return -1; // 无法到达终点
}// 示例测试
console.log(minInitialFuel([[10, 20], [30, 40]])); // 输出:70
console.log(minInitialFuel([[-1, 20, 0], [30, 0, 40], [50, 60, 70]])); // 输出:100
console.log(minInitialFuel([[0, 10], [20, 30]])); // 输出:-1

代码详解

  1. PriorityQueue类

    • enqueue：将元素按maxSoFar升序插入队列，模拟优先队列。
    • dequeue：取出队列首部元素（最优路径）。

  2. 初始化状态

    if (startVal === -1) {// 起点是加油站，初始油量100pq.enqueue({ currentSegment: 0, maxSoFar: 0 });
} else {// 普通起点，初始油耗为格子值pq.enqueue({ currentSegment: initialCost, maxSoFar: initialCost });
}
    • 根据起点是否为加油站初始化不同状态。

  3. 方向遍历

    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    • 上下左右四个移动方向。

  4. 状态处理逻辑

    • 障碍物跳过：若目标格子值为0，直接跳过。
    • 加油站处理：重置区段累计为0，并更新最大油耗。
    • 油量溢出检查：区段累计超过100时无法移动。

  5. 访问状态管理

    const newKey = `${ni},${nj},${newSegmentAfter}`;
if (!visited.has(newKey) || newMax < visited.get(newKey)) {visited.set(newKey, newMax);pq.enqueue(...);
}
    • 使用Map记录每个状态的最优解，避免重复处理。

示例测试

  1. 示例1：路径右→下，总油耗70。
  2. 示例2：路径包含加油站，初始油量100。
  3. 示例3：起点障碍物，无法到达。

综合分析

  1. 时间复杂度

    • 最坏情况O(MN100)，优先队列保证每次扩展最优路径。

  2. 空间复杂度

    • 存储状态信息O(MN100)，记录每个位置的区段累计和最大油耗。

  3. 正确性

    • 严格处理加油站、障碍物和油量限制，确保找到最优解。

  4. 适用性

    • 适用于小规模地图，代码直观易维护。

C++

问题分析

汽车需要从地图左上角移动到右下角，每个格子可能有油量消耗、加油站或障碍物。要求计算到达终点的最小初始油量（路径中最大的区段累计消耗），若无法到达则返回-1。

解题思路

  1. Dijkstra算法：使用优先队列按路径最大油量排序，优先扩展更优路径。
  2. 状态管理：记录当前位置、当前区段累计油耗、全局最大油耗。
  3. 加油站处理：到达加油站时重置当前区段累计为0。
  4. 障碍物处理：直接跳过值为0的格子。

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;struct State {int i, j;int current_segment; // 当前区段累计油耗int max_so_far;      // 路径中的最大油耗State(int i, int j, int cs, int m) : i(i), j(j), current_segment(cs), max_so_far(m) {}// 优先队列按max_so_far从小到大排序bool operator>(const State& other) const {return max_so_far > other.max_so_far;}
};int minInitialFuel(vector<vector<int>>& grid) {int m = grid.size();if (m == 0) return -1;int n = grid[0].size();// 起点是障碍物if (grid[0][0] == 0) return -1;// dist[i][j][k] = 到达(i,j)且当前区段累计k时的最小全局maxvector<vector<vector<int>>> dist(m, vector<vector<int>>(n, vector<int>(101, INT_MAX)));priority_queue<State, vector<State>, greater<State>> pq;// 初始化起点if (grid[0][0] == -1) {pq.push(State(0, 0, 0, 0));dist[0][0][0] = 0;} else {int cost = grid[0][0];pq.push(State(0, 0, cost, cost));dist[0][0][cost] = cost;}vector<pair<int, int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};while (!pq.empty()) {State s = pq.top();pq.pop();// 到达终点if (s.i == m-1 && s.j == n-1) return s.max_so_far;// 如果当前状态不是最优，跳过if (s.max_so_far > dist[s.i][s.j][s.current_segment]) continue;for (auto& dir : dirs) {int ni = s.i + dir.first;int nj = s.j + dir.second;if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;int cell_val = grid[ni][nj];if (cell_val == 0) continue; // 障碍物int cost = (cell_val == -1) ? 0 : cell_val;int new_segment = s.current_segment + cost;bool is_gas = (cell_val == -1);// 油量溢出检查if (new_segment > 100) continue;// 更新全局最大油耗int new_max = max(s.max_so_far, new_segment);// 处理加油站int new_segment_after = is_gas ? 0 : new_segment;// 更新状态if (new_max < dist[ni][nj][new_segment_after]) {dist[ni][nj][new_segment_after] = new_max;pq.push(State(ni, nj, new_segment_after, new_max));}}}return -1; // 无法到达
}int main() {vector<vector<int>> example1 = {{10, 20},{30, 40}};cout << minInitialFuel(example1) << endl; // 输出:70vector<vector<int>> example2 = {{-1, 20, 0},{30, 0, 40},{50, 60, 70}};cout << minInitialFuel(example2) << endl; // 输出:100vector<vector<int>> example3 = {{0, 10},{20, 30}};cout << minInitialFuel(example3) << endl; // 输出:-1return 0;
}

代码详解

  1. State结构体

    • 保存当前位置(i,j)、当前区段累计油耗current_segment、路径最大油耗max_so_far。
    • 重载>运算符实现最小优先队列。

  2. 三维dist数组

    • dist[i][j][k]表示到达(i,j)且当前区段累计为k时的最小全局最大油耗。
    • 初始值为INT_MAX，用于剪枝非最优路径。

  3. 优先队列初始化

    • 起点是加油站时，current_segment=0，否则初始化为起点格子的油耗。

  4. 方向遍历与状态扩展

    • 遍历上下左右四个方向，跳过障碍物和越界位置。
    • 计算新区段累计油耗，若超过100则跳过。
    • 遇到加油站时重置区段累计为0，并更新全局最大值。

  5. 状态更新条件

    • 若新状态的new_max比已记录的值更小，则更新dist并加入队列。

示例测试

  1. 示例1：路径中最大累计油耗为10+20+40=70。
  2. 示例2：通过加油站补充油量，最大累计为100。
  3. 示例3：起点障碍物直接返回-1。

综合分析

  1. 时间复杂度

    • 最坏情况O(MN100 log(MN100))，优先队列保证每次处理最优路径。

  2. 空间复杂度

    • 三维数组dist占用O(MN100)空间。

  3. 正确性

    • 严格处理加油站重置逻辑，全局最大值跟踪确保结果正确。

  4. 适用性

    • 使用C++ STL高效实现，适用于题目约束范围内的所有输入。

C

问题分析

汽车需要从地图左上角移动到右下角，每个格子可能有油量消耗、加油站或障碍物。要求找到到达终点的最小初始油量（路径中最大的区段累计消耗），若无法到达返回-1。

解题思路

  1. 优先队列（Dijkstra算法）：按路径最大油量排序，优先扩展更优路径。
  2. 状态管理：记录当前位置、当前区段累计油耗、全局最大油耗。
  3. 加油站处理：到达加油站时重置当前区段累计为0，并更新全局最大值。
  4. 障碍物处理：直接跳过值为0的格子。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>typedef struct {int i, j;int current_segment; // 当前区段累计油耗int max_so_far;      // 路径中的最大油耗
} State;typedef struct {State* data;int size;int capacity;
} PriorityQueue;void shift_up(State* data, int index) {while (index > 0) {int parent = (index - 1) / 2;if (data[index].max_so_far >= data[parent].max_so_far) break;State temp = data[index];data[index] = data[parent];data[parent] = temp;index = parent;}
}void shift_down(State* data, int size, int index) {int left = 2 * index + 1;int right = 2 * index + 2;int smallest = index;if (left < size && data[left].max_so_far < data[smallest].max_so_far) smallest = left;if (right < size && data[right].max_so_far < data[smallest].max_so_far) smallest = right;if (smallest != index) {State temp = data[index];data[index] = data[smallest];data[smallest] = temp;shift_down(data, size, smallest);}
}PriorityQueue* createPriorityQueue() {PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));pq->data = NULL;pq->size = 0;pq->capacity = 0;return pq;
}void push(PriorityQueue* pq, State state) {if (pq->size >= pq->capacity) {pq->capacity = pq->capacity ? pq->capacity * 2 : 1;pq->data = realloc(pq->data, pq->capacity * sizeof(State));}pq->data[pq->size] = state;shift_up(pq->data, pq->size);pq->size++;
}State pop(PriorityQueue* pq) {State res = pq->data[0];pq->data[0] = pq->data[pq->size - 1];pq->size--;shift_down(pq->data, pq->size, 0);return res;
}int empty(PriorityQueue* pq) {return pq->size == 0;
}void freePriorityQueue(PriorityQueue* pq) {free(pq->data);free(pq);
}int minInitialFuel(int** grid, int gridSize, int* gridColSize) {int m = gridSize, n = gridColSize[0];if (grid[0][0] == 0) return -1;// 初始化三维数组 dist[i][j][k] 表示到达 (i,j) 且当前区段为 k 的最小全局最大值int*** dist = (int***)malloc(m * sizeof(int**));for (int i = 0; i < m; i++) {dist[i] = (int**)malloc(n * sizeof(int*));for (int j = 0; j < n; j++) {dist[i][j] = (int*)malloc(101 * sizeof(int));for (int k = 0; k <= 100; k++) dist[i][j][k] = INT_MAX;}}PriorityQueue* pq = createPriorityQueue();if (grid[0][0] == -1) {push(pq, (State){0, 0, 0, 0});dist[0][0][0] = 0;} else {int initialCost = grid[0][0];if (initialCost > 100) {for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) free(dist[i][j]);free(dist[i]);}free(dist);freePriorityQueue(pq);return -1;}push(pq, (State){0, 0, initialCost, initialCost});dist[0][0][initialCost] = initialCost;}int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};while (!empty(pq)) {State s = pop(pq);if (s.i == m - 1 && s.j == n - 1) {for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) free(dist[i][j]);free(dist[i]);}free(dist);freePriorityQueue(pq);return s.max_so_far;}if (s.max_so_far > dist[s.i][s.j][s.current_segment]) continue;for (int d = 0; d < 4; d++) {int ni = s.i + dirs[d][0], nj = s.j + dirs[d][1];if (ni < 0 || ni >= m || nj < 0 || nj >= n || grid[ni][nj] == 0) continue;int cost = (grid[ni][nj] == -1) ? 0 : grid[ni][nj];int new_segment = s.current_segment + cost;if (new_segment > 100) continue;int new_max = (s.max_so_far > new_segment) ? s.max_so_far : new_segment;int new_segment_after = (grid[ni][nj] == -1) ? 0 : new_segment;if (new_max < dist[ni][nj][new_segment_after]) {dist[ni][nj][new_segment_after] = new_max;push(pq, (State){ni, nj, new_segment_after, new_max});}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) free(dist[i][j]);free(dist[i]);}free(dist);freePriorityQueue(pq);return -1;
}int main() {int row1[] = {10, 20}, row2[] = {30, 40};int* grid1[] = {row1, row2}, cols1[] = {2, 2};printf("%d\n", minInitialFuel(grid1, 2, cols1)); // 70int row3[] = {-1, 20, 0}, row4[] = {30, 0, 40}, row5[] = {50, 60, 70};int* grid2[] = {row3, row4, row5}, cols2[] = {3, 3, 3};printf("%d\n", minInitialFuel(grid2, 3, cols2)); // 100int row6[] = {0, 10}, row7[] = {20, 30};int* grid3[] = {row6, row7}, cols3[] = {2, 2};printf("%d\n", minInitialFuel(grid3, 2, cols3)); // -1return 0;
}

代码详解

  1. 数据结构

    • State：存储位置、当前区段累计油耗、路径最大油耗。
    • PriorityQueue：基于堆的优先队列，按max_so_far升序排列。

  2. 输入处理

    • 检查起点是否为障碍物（grid[0][0] == 0），直接返回-1。

  3. 初始化三维数组

    • dist[i][j][k]表示到达(i,j)且当前区段累计为k时的最小全局最大值。

  4. 优先队列初始化

    • 若起点是加油站，初始油量为0；否则检查初始油耗是否超过100。

  5. 状态扩展

    • 遍历四个方向，跳过障碍物和越界位置。
    • 计算新区段累计油耗，若超过100则跳过。
    • 更新全局最大值并处理加油站逻辑（重置区段为0）。

  6. 内存管理

    • 在每次返回前释放动态分配的内存，避免内存泄漏。

示例测试

  1. 示例1：路径右→下，总消耗70。
  2. 示例2：通过加油站补充油量，总消耗100。
  3. 示例3：起点障碍物，返回-1。

综合分析

  1. 时间复杂度

    • 最坏情况为O(M*N*100 log(M*N*100))，优先队列保证每次处理最优路径。

  2. 空间复杂度

    • 三维数组dist占用O(M*N*100)空间。

  3. 正确性

    • 严格处理加油站、障碍物和油量限制，确保结果正确。

  4. 适用性

    • 适用于小规模地图，代码结构清晰，内存管理严格。

GO

问题分析

汽车需要从地图左上角移动到右下角，每个格子可能有油量消耗、加油站或障碍物。要求找到到达终点的最小初始油量（路径中最大的区段累计消耗），若无法到达返回-1。

解题思路

  1. Dijkstra算法：使用优先队列按路径最大油量排序，优先扩展更优路径。
  2. 状态管理：记录当前位置、当前区段累计油耗、全局最大油耗。
  3. 加油站处理：到达加油站时重置当前区段累计为0，并更新全局最大值。
  4. 障碍物处理：直接跳过值为0的格子。

代码实现

package mainimport ("container/heap""fmt""math"
)// 定义状态结构体
type State struct {i, j           int // 当前位置currentSegment int // 当前区段累计油耗maxSoFar       int // 路径中的最大油耗
}// 优先队列实现
type PriorityQueue []*Statefunc (pq PriorityQueue) Len() int { return len(pq) }// 按 maxSoFar 从小到大排序
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].maxSoFar < pq[j].maxSoFar }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }func (pq *PriorityQueue) Push(x interface{}) {*pq = append(*pq, x.(*State))
}func (pq *PriorityQueue) Pop() interface{} {old := *pqn := len(old)item := old[n-1]*pq = old[:n-1]return item
}func minInitialFuel(grid [][]int) int {m := len(grid)if m == 0 {return -1}n := len(grid[0])if grid[0][0] == 0 {return -1 // 起点是障碍物}// 初始化优先队列pq := make(PriorityQueue, 0)heap.Init(&pq)// visited[i][j][k] 表示到达 (i,j) 且当前区段为 k 的最小全局最大值visited := make(map[string]int)// 处理起点start := grid[0][0]if start == -1 {heap.Push(&pq, &State{0, 0, 0, 0})visited[key(0, 0, 0)] = 0} else {initialCost := startif initialCost > 100 {return -1}heap.Push(&pq, &State{0, 0, initialCost, initialCost})visited[key(0, 0, initialCost)] = initialCost}// 四个方向dirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}for pq.Len() > 0 {current := heap.Pop(&pq).(*State)// 到达终点if current.i == m-1 && current.j == n-1 {return current.maxSoFar}// 跳过非最优路径currentKey := key(current.i, current.j, current.currentSegment)if val, exists := visited[currentKey]; exists && val < current.maxSoFar {continue}// 遍历四个方向for _, dir := range dirs {ni, nj := current.i+dir[0], current.j+dir[1]if ni < 0 || nj < 0 || ni >= m || nj >= n {continue}cellVal := grid[ni][nj]if cellVal == 0 {continue // 障碍物}// 计算新区段油耗cost := cellValisGasStation := cellVal == -1if isGasStation {cost = 0}newSegment := current.currentSegment + cost// 油量溢出检查if newSegment > 100 {continue}// 更新全局最大值newMax := max(current.maxSoFar, newSegment)// 处理加油站newSegmentAfter := newSegmentif isGasStation {newSegmentAfter = 0}// 生成新状态的唯一标识newKey := key(ni, nj, newSegmentAfter)if val, exists := visited[newKey]; !exists || newMax < val {visited[newKey] = newMaxheap.Push(&pq, &State{i:             ni,j:             nj,currentSegment: newSegmentAfter,maxSoFar:      newMax,})}}}return -1
}// 生成状态唯一标识
func key(i, j, segment int) string {return fmt.Sprintf("%d-%d-%d", i, j, segment)
}// 示例测试
func main() {example1 := [][]int{{10, 20},{30, 40},}fmt.Println(minInitialFuel(example1)) // 输出:70example2 := [][]int{{-1, 20, 0},{30, 0, 40},{50, 60, 70},}fmt.Println(minInitialFuel(example2)) // 输出:100example3 := [][]int{{0, 10},{20, 30},}fmt.Println(minInitialFuel(example3)) // 输出:-1
}

代码详解

  1. State结构体

    • 存储当前位置 (i,j)、当前区段累计油耗 currentSegment、路径最大油耗 maxSoFar。

  2. 优先队列实现

    • 使用 container/heap 包实现优先队列，按 maxSoFar 从小到大排序。
    • Push 和 Pop 方法用于操作堆结构。

  3. 状态初始化

    • 起点是加油站时，初始化 currentSegment 为0；否则检查初始油耗是否合法。

  4. 方向遍历

    • 上下左右四个方向，跳过越界和障碍物。

  5. 油量计算逻辑

    • 遇到加油站时重置区段累计为0。
    • 检查油量溢出（超过100则跳过）。

  6. 状态更新

    • 使用 map 记录每个状态的最小全局最大值，避免重复处理。

示例测试

  1. 示例1：路径右→下，总消耗70。
  2. 示例2：通过加油站补充油量，总消耗100。
  3. 示例3：起点障碍物，返回-1。

综合分析

  1. 时间复杂度

    • 最坏情况为 O(M*N*100 log(M*N*100))，优先队列保证每次处理最优路径。

  2. 空间复杂度

    • 使用 map 存储状态信息，空间复杂度为 O(M*N*100)。

  3. 正确性

    • 严格处理加油站、障碍物和油量限制，确保找到最优解。

  4. 适用性

    • 代码利用Go的 container/heap 实现高效优先队列，适用于小规模地图。

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！

http://www.xdnf.cn/news/3783.html

相关文章：

  • 什么是函数重载？
  • MySQL 空值处理函数对比：IFNULL、COALESCE 和 NULLIF
  • 《Linux macOS ：GCC升级方法》
  • 私人医生通过AI分析基因数据，是否有权提前告知癌症风险？
  • 【AI面试准备】XMind拆解业务场景识别AI赋能点
  • QML图像提供器 (Image Provider)
  • 【Ansible自动化运维实战：从Playbook到负载均衡指南】
  • 【算法基础】插入排序算法 - JAVA
  • 怎样增加AI对话的拟人化和增加同理心
  • WEB前端小练习——记事本
  • 先知AIGC超级工场，撬动运营效率新杠杆
  • 在 Trae CN IDE 中配置 Python 3.11的指南
  • Nat. Hum. Behav：大脑“变形记”，注意力错误下的空间认知奇遇
  • 如何解决 403 错误：请求被拒绝，无法连接到服务器
  • 【KWDB 创作者计划】Docker单机环境下KWDB集群快速搭建指南
  • with的用法
  • 家用服务器 Ubuntu 服务器配置与 Cloudflare Tunnel 部署指南
  • 【中间件】brpc_基础_用户态线程上下文
  • 小程序与快应用：中国移动互联网的渐进式革命——卓伊凡的技术演进观
  • JavaScript性能优化实战之调试与性能检测工具
  • KeyPresser 一款自动化按键工具
  • 【c语言】数据在内存中的存储
  • Servlet（二）
  • 怎样提升社交机器人闲聊能力
  • 【Linux】进程优先级与进程切换理解
  • 第38课 常用快捷操作——双击“鼠标左键”进入Properties Panel
  • Linux运维——Vim技巧一
  • LeetCode —— 102. 二叉树的层序遍历
  • 设计模式简述（十七）备忘录模式
  • yolov5 train笔记4 roboflow