智能驾驶-C++（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];
// 如果下一个位置超出边界或者是障碍物则跳过
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
continue;
if (mp[nx][ny] == 0) // 障碍物不可走
continue;
int nxtval = 0;
if (mp[nx][ny] > 0) // 如果当前位置为耗油量
nxtval = dis[x][y] + mp[nx][ny];
if (nxtval > 100) // 超过油箱容量的不考虑
continue;
if (dis[nx][ny] > nxtval) { // 如果找到更短的路径则更新
dis[nx][ny] = nxtval;
if (!vis[nx][ny]) {
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
}
int ans = -1;
if (dis[0][0] <= 100) // 如果起点的最短路径油量不超过100
ans = dis[0][0];
cout << ans << endl;
return 0;
}
AI助手
全部评论 (0)
还没有任何评论哟~