2024年华为OD机试真题-智能驾驶

华为OD机试真题-智能驾驶-2024年OD统一考试（D卷）

题目描述：

有一辆汽车需要从 m*n 的地图的左上角(起点)开往地图的右下角(终点)，去往每一个地区都需要消耗一定的油量，加油站可进行加油

请你计算汽车确保从起点到达终点时所需的最少初始油量说明:

(1) 智能汽车可以上下左右四个方向移动1

(2) 地图上的数字取值是 0或-1 或者正整数:

1: 表示加油站，可以加满油，汽车的油箱容量最大为 100;

0: 表示这个地区是障碍物，汽车不能通过\n正整数: 表示汽车走过这个地区的耗油量

(3) 如果汽车无论如何都无法到达终点，则返回 -1

输入描述：

第一行为两个数字，M，V，表示地图的大小为 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

******************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************

******************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************

******************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************

解题思路：本题可以看作是一种有负权边的最短路，使用SPAF算法即可。

c++代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
// 用于读取一行输入并将其分割成整数向量
vector<int> line2vec() {
    string line;
    getline(cin, line);
    istringstream iss(line);
    vector<int> res;
    string token;
    while (getline(iss, token, ',')) // 通过逗号分隔读取数字
        res.push_back(stoi(token)); // 将读取的字符串转换为整数
    return res;
}
 
int n, m; // n, m 分别为网格的行数和列数
int dx[] = {1, 0, -1, 0}; // 表示移动方向，分别为下、右、上、左（x 方向移动）
int dy[] = {0, 1, 0, -1}; // 表示移动方向，分别为下、右、上、左（y 方向移动）
vector<vector<int>> mp; // 存储网格信息
vector<vector<bool>> vis; // 访问标记数组
vector<vector<int>> dis; // 存储从终点到各点的最短距离
 
// 主函数
signed main() {
    vector<int> v = line2vec(); // 读取网格尺寸
    n = v[0]; // 行数
    m = v[1]; // 列数
    for (int i = 0; i < n; i++) {
        mp.push_back(line2vec()); // 读取每行的网格信息
        vis.push_back(vector<bool>(m, 0)); // 初始化访问标记数组
        dis.push_back(vector<int>(m, 1e9)); // 初始化最短距离数组，用非常大的数表示
    }
    // 初始化终点的距离为终点本身的耗油量
    dis[n-1][m-1] = mp[n-1][m-1]; // 终点的耗油量为其自身值
    vis[n-1][m-1] = 1; // 标记终点已访问
    queue<pair<int,int>> q; // 使用队列进行BFS
    q.push({n-1, m-1}); // 从终点开始遍历
    
    // BFS 过程
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop();
        vis[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];			// 计算下一个位置的坐标
            int ny = y + dy[i];