华为OD机试真题 - 智能驾驶 (D卷,200分)
题目描述
有一辆汽车需要从 m * n 的地图左上角（起点）开往地图的右下角（终点），去往每一个地区都需要消耗一定的油量，加油站可进行加油。
请你计算汽车确保从从起点到达终点时所需的最少初始油量。
说明：
- 智能汽车可以上下左右四个方向移动
- 地图上的数字取值是 0 或 -1 或 正整数： -1 ：表示加油站，可以加满油，汽车的油箱容量最大为100； 0 ：表示这个地区是障碍物，汽车不能通过 正整数：表示汽车走过这个地区的耗油量\
- 如果汽车无论如何都无法到达终点，则返回 -1
目录
题目描述
输入描述
输出描述
用例
题目解析
Java算法源码
JS算法源码
Python算法源码
C算法源码
华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作
https://ac.nowcoder.com/acm/contest/5652/K
点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。
输入描述
第一行为两个数字，M，N，表示地图的大小为 M * N
- 0 < M,N ≤ 200
后面一个 M * N 的矩阵，其中的值是 0 或 -1 或正整数，加油站的总数不超过 200 个
输出描述
如果汽车无论如何都无法到达终点，则返回 -1
如果汽车可以到达终点，则返回最少的初始油量
用例
题目解析
- 创建一个优先队列（以油量为键），并将起点
(0, 0, 0)加入队列。（这里假设起始油量为0，因为我们要找的是最少初始油量） - 创建一个集合或数组来记录已经访问过的状态，以避免重复搜索。
- 当队列不为空时，执行以下操作： a. 弹出队列中油量最少的节点
(x, y, oil)。 b. 如果(x, y)是终点，那么我们找到了一条路径，返回oil即为所求。 c. 否则，遍历该节点的所有合法邻居（即没有障碍物并且不超出边界的节点）。 d. 对于每个邻居(nx, ny)，计算经过该邻居后的油量newOil = oil - cost[nx][ny]，如果newOil < 0则忽略该邻居（因为不能到达）。 e. 如果(nx, ny, newOil)未被访问过，将其加入优先队列，并标记为已访问。 - 如果队列变空也没有找到终点，说明无法到达，返回
-1。
注意：
- 在步骤3中，每次移动到加油站时，需要将油量设为最大值（例如100），这代表加满油。
- 在实际应用中，可能需要优化算法来减少搜索空间，例如通过剪枝技巧去除明显不可达的状态。
JS算法源码
const readline = require("readline");
const rl = readline.createInterface({ input: process.stdin });
(async function () {
const [m, n] = (await new Promise((resolve) => rl.question("", resolve))).split(",").map(Number);
const matrix = [];
for (let i = 0; i < m; i++) {
matrix.push((await new Promise((resolve) => rl.question("", resolve))).split(",").map(Number));
}
const offsets = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
class Node {
constructor(x, y) {
this.x = x;
this.y = y;
this.init = 0;
this.remain = 0;
this.flag = false;
}
}
function bfs() {
if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
return -1;
}
const queue = [];
const src = new Node(0, 0);
if (matrix[0][0] == -1) {
src.init = 0;
src.remain = 100;
src.flag = true;
} else {
src.init = matrix[0][0];
src.remain = 0;
src.flag = false;
}
queue.push(src);
const dist_init = Array.from({ length: m }, () => Array(n).fill(Infinity));
const dist_remain = Array.from({ length: m }, () => Array(n).fill(0));
dist_init[0][0] = src.init;
dist_remain[0][0] = src.remain;
while (queue.length > 0) {
const cur = queue.shift();
for (let [offsetX, offsetY] of offsets) {
const newX = cur.x + offsetX;
const newY = cur.y + offsetY;
if (
newX < 0 ||
newX >= m ||
newY < 0 ||
newY >= n ||
matrix[newX][newY] == 0
) {
continue;
}
let init = cur.init;
let remain = cur.remain;
let flag = cur.flag;
if (matrix[newX][newY] == -1) {
remain = 100;
flag = true;
} else {
remain -= matrix[newX][newY];
}
if (remain < 0) {
if (flag) {
continue;
} else {
init -= remain;
remain = 0;
}
}
if (init > 100) {
continue;
}
if (init > dist_init[newX][newY]) {
continue;
}
if (init < dist_init[newX][newY] || remain > dist_remain[newX][newY]) {
dist_init[newX][newY] = init;
dist_remain[newX][newY] = remain;
const next = new Node(newX, newY);
next.init = init;
next.remain = remain;
next.flag = flag;
queue.push(next);
}
}
}
return dist_init[m - 1][n - 1] == Infinity ? -1 : dist_init[m - 1][n - 1];
}
console.log(bfs());
})();
Java算法源码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int m;
static int n;
static int[][] matrix;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
matrix = new int[m][n];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
matrix[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(bfs());
}
// 上下左右四个方向对应的偏移量
static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 记录路径中位置的几个状态
static class Node {
int x; // 位置横坐标
int y; // 位置纵坐标
int init; // 到达此位置所需的最少初始油量
int remain; // 到达此位置时剩余可用油量
boolean flag; // 到达此位置前有没有加过油
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int bfs() {
// 如果左上角和右下角不可达，则直接返回-1
if (matrix[0][0] == 0 || matrix[m - 1][n - 1] == 0) {
return -1;
}
// 广搜队列
ArrayList<Node> queue = new ArrayList<>();
// 起始位置
Node src = new Node(0, 0);
if (matrix[0][0] == -1) {
// 如果起始位置就是加油站，则到达(0,0)位置所需初始油量为0，且剩余可用油量为100，且需要标记已加油
src.init = 0;
src.remain = 100;
src.flag = true;
} else {
// 如果起始位置不是加油站，则到达(0,0)位置所需的初始油量至少为matrix[0][0], 剩余可用油量为0，未加油状态
src.init = matrix[0][0];
src.remain = 0;
src.flag = false;
}
queue.add(src);
// dist_init[x][y] 用于记录起点 (0, 0) 到达 (x, y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的初始油量
int[][] dist_init = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 由于需要记录每个位置的最少需要的初始油量，因此每个位置所需的初始油量初始化为一个较大值
dist_init[i][j] = Integer.MAX_VALUE;
}
}
// dist_remain 用于记录起点 (0,0) 到达 (x,y) 的所有可达路径中最优路径（即初始油量需求最少的路径）的最大剩余可用油量
// 即如果存在多条最优路径，我们应该选这些路径中到达此位置剩余油量最多的
int[][] dist_remain = new int[m][n];
// 起点（0,0）自身到达自身位置（0,0）所需的最少初始油量和最多剩余油量
dist_init[0][0] = src.init;
dist_remain[0][0] = src.remain;
// 广搜
while (queue.size() > 0) {
Node cur = queue.remove(0);
// 从当前位置cur开始向上下左右四个方向探路
for (int[] offset : offsets) {
// 新位置
int newX = cur.x + offset[0];
int newY = cur.y + offset[1];
// 新位置越界 或者 新位置是障碍，则新位置不可达，继续探索其他方向
if (newX < 0 || newX >= m || newY < 0 || newY >= n || matrix[newX][newY] == 0) continue;
// 如果新位置可达，则计算到达新位置的三个状态数据
int init = cur.init; // 到达新位置所需的最少初始油量
int remain = cur.remain; // 到达新位置时还剩余的最多可用油量
boolean flag = cur.flag; // 是否加油了
if (matrix[newX][newY] == -1) {
// 如果新位置是加油站，则加满油
remain = 100;
// 标记加过油了
flag = true;
} else {
// 如果新位置不是加油站，则需要消耗matrix[newX][newY]个油
remain -= matrix[newX][newY];
}
// 如果到达新位置后，剩余油量为负数
if (remain < 0) {
if (flag) {
// 如果之前已经加过油了，则说明到达此路径前是满油状态，因此我们无法从初始油量里面"借"油
continue;
} else {
// 如果之前没有加过油，则超出的油量（-remain），可以从初始油量里面"借"，即需要初始油量 init + (-remain) 才能到达新位置
init -= remain;
// 由于初始油量 init + (-remain) 刚好只能支持汽车到达新位置，因此汽车到达新位置后剩余可用油量为0
remain = 0;
}
}
// 如果到达新位置所需的初始油量超过了满油100，则无法到达新位置
if (init > 100) {
continue;
}
// 如果可达新位置，则继续检查当前路径策略到达新位置(newX, newY)所需的初始油量init是否比其他路径策略更少
if (init > dist_init[newX][newY]) {
// 如果不是，则无需探索新位置(newX, newY)
continue;
}
// 当前路径策略到达新位置(newX,newY)所需初始油量init更少，或者，init和前面路径策略相同，但是当前路径策略剩余可用油量remain更多
if (init < dist_init[newX][newY] || remain > dist_remain[newX][newY]) {
// 则当前路径策略更优，记录更优路径的状态
dist_init[newX][newY] = init;
dist_remain[newX][newY] = remain;
// 将当前新位置加入BFS队列
Node next = new Node(newX, newY);
next.init = init;
next.remain = remain;
next.flag = flag;
queue.add(next);
}
}
}
// dist_init[m - 1][n - 1] 记录的是到达右下角终点位置所需的最少初始油量
return dist_init[m - 1][n - 1] == Integer.MAX_VALUE ? -1 : dist_init[m - 1][n - 1];
}
}
Python算法源码
import sys
from collections import deque
# 输入获取
m, n = map(int, input().split(","))
matrix = [list(map(int, input().split(","))) for _ in range(m)]
# 上下左右四个方向对应的偏移量
offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
# 记录路径中位置的几个状态
class Node:
def __init__(self, x, y):
self.x = x # 位置横坐标
self.y = y # 位置纵坐标
self.init = 0 # 到达此位置所需的最少初始油量
self.remain = 0 # 到达此位置时剩余可用油量
self.flag = False # 到达此位置前有没有加过油
# 算法入口
def bfs():
if matrix[0][0] == 0 or matrix[m - 1][n - 1] == 0:
return -1
queue = deque()
src = Node(0, 0)
if matrix[0][0] == -1:
src.init = 0
src.remain = 100
src.flag = True
else:
src.init = matrix[0][0]
src.remain = 0
src.flag = False
queue.append(src)
dist_init = [[sys.maxsize] * n for _ in range(m)]
dist_remain = [[0] * n for _ in range(m)]
dist_init[0][0] = src.init
dist_remain[0][0] = src.remain
while queue:
cur = queue.popleft()
for offsetX, offsetY in offsets:
newX = cur.x + offsetX
newY = cur.y + offsetY
if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 0:
continue
init = cur.init
remain = cur.remain
flag = cur.flag
if matrix[newX][newY] == -1:
remain = 100
flag = True
else:
remain -= matrix[newX][newY]
if remain < 0:
if flag:
continue
else
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2024华为OD机试题库D卷 文章被收录于专栏
2024年5-11月份考的D卷，不用再看AB卷，CD卷题目一样。多种语言解法，欢迎提供更好的解法。
查看1道真题和解析
投递华为等公司10个岗位 >