#P3259. 智能驾驶(200分)
-
1000ms
Tried: 126
Accepted: 26
Difficulty: 7
所属公司 :
华为od
智能驾驶(200分)
思路:二分答案+dijkstra枚举
可以考虑这样一个问题,当初始的油量越高,越容易抵达终点,因此具有单调性,可以使用二分查找来查询最少需要的初始油量。
然后我们再枚举答案为x时,我们需要使用dijkstra查询当前油量是否可以到达终点,如果可以,则r=mid,否则l=mid+1
具体思路可以查看下面的代码细节。
JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n, m;
let mp = [];
rl.on('line', (line) => {
if (!n) {
// 读取第一行输入,获取矩阵的行数 n 和列数 m
[n, m] = line.split(',').map(Number);
} else {
// 读取矩阵的每一行输入
mp.push(line.split(',').map(Number));
if (mp.length === n) {
// 当读取完整个矩阵后执行以下操作
const check = (mid) => {
// 定义检查函数,判断是否存在路径使得路径上的数字之和不小于 mid
// 初始化距离数组 dis 和访问标记数组 vis
const dis = Array.from({ length: n }, () => Array(m).fill(-1));
const vis = Array.from({ length: n }, () => Array(m).fill(false));
// 初始位置的距离
dis[0][0] = mid - mp[0][0];
if (mp[0][0] === -1) dis[0][0] = 100;
else if (mp[0][0] === 0 || dis[0][0] < 0) return false;
// 定义广度优先搜索的队列
const q = [];
q.push([-dis[0][0], 0, 0]);
const tx = [0, 1, 0, -1];
const ty = [1, 0, -1, 0];
while (q.length !== 0) {
const [w, x, y] = q.pop();
const ww = -w;
if (vis[x][y]) continue;
vis[x][y] = true;
// 遍历四个方向
for (let i = 0; i < 4; i++) {
const xx = x + tx[i];
const yy = y + ty[i];
let newW = 0;
// 判断是否在矩阵范围内,且未访问过,且当前位置的数字满足条件
if (0 <= xx && xx < n && 0 <= yy && yy < m && mp[xx][yy] !== 0 && !vis[xx][yy] && mp[xx][yy] <= ww) {
if (mp[xx][yy] === -1) newW = 100;
else newW = ww - mp[xx][yy];
if (newW > dis[xx][yy]) {
dis[xx][yy] = newW;
q.push([-newW, xx, yy]);
}
}
}
}
// 判断右下角是否被访问到
return vis[n - 1][m - 1];
};
// 二分搜索
let L = 0;
let R = 100;
let ans = -1;
while (L <= R) {
const mid = Math.floor((L + R) / 2);
if (check(mid)) {
ans = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
// 输出结果
console.log(ans);
rl.close();
}
}
});
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
// 使用 Scanner 读取输入,设置分隔符为逗号或空白字符
Scanner scanner = new Scanner(System.in).useDelimiter(",|\\s+");
int n = scanner.nextInt(); // 读取矩阵的行数
int m = scanner.nextInt(); // 读取矩阵的列数
int[][] mp = new int[n][m]; // 存储矩阵的二维数组
// 读取矩阵的每一个元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mp[i][j] = scanner.nextInt();
}
}
int L = 0, R = 100, ans = -1; // 二分查找的边界和结果
// 二分查找
while (L <= R) {
int mid = (L + R) / 2;
if (check(mp, mid, n, m)) { // 判断是否存在满足条件的路径
ans = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
System.out.println(ans); // 输出结果
}
// 检查是否存在满足条件的路径
public static boolean check(int[][] mp, int mid, int n, int m) {
int[][] dis = new int[n][m]; // 存储距离的数组
boolean[][] vis = new boolean[n][m]; // 存储访问标记的数组
for (int i = 0; i < n; i++) {
Arrays.fill(dis[i], -1);
}
dis[0][0] = mid - mp[0][0];
if (mp[0][0] == -1) {
dis[0][0] = 100;
} else if (mp[0][0] == 0 || dis[0][0] < 0) {
return false;
}
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[0] - a[0]); // 使用优先队列存储状态
q.offer(new int[] {dis[0][0], 0, 0}); // 将初始状态加入队列
int[] tx = {0, 1, 0, -1}; // x 方向的偏移量
int[] ty = {1, 0, -1, 0}; // y 方向的偏移量
while (!q.isEmpty()) {
int[] cur = q.poll();
int w = cur[0], x = cur[1], y = cur[2];
if (vis[x][y]) {
continue;
}
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int xx = x + tx[i], yy = y + ty[i], ww = 0;
if (xx >= 0 && xx < n && yy >= 0 && yy < m && mp[xx][yy] != 0 && !vis[xx][yy] && mp[xx][yy] <= w) {
if (mp[xx][yy] == -1) {
ww = 100;
} else {
ww = w - mp[xx][yy];
}
if (ww > dis[xx][yy]) {
dis[xx][yy] = ww;
q.offer(new int[] {dis[xx][yy], xx, yy});
}
}
}
}
return vis[n - 1][m - 1];
}
}
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 检查是否存在满足条件的路径
bool check(int mid, int n, int m, vector<vector<int>>& mp) {
vector<vector<int>> dis(n, vector<int>(m, -1)); // 存储距离的二维数组
vector<vector<bool>> vis(n, vector<bool>(m, false)); // 存储访问标记的二维数组
dis[0][0] = mid - mp[0][0]; // 初始位置的距离
if (mp[0][0] == -1) {
dis[0][0] = 100;
} else if (mp[0][0] == 0 || dis[0][0] < 0) {
return false;
}
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q; // 使用优先队列存储状态
q.push({-dis[0][0], 0, 0}); // 将初始状态加入队列
int tx[] = {0, 1, 0, -1}; // x 方向的偏移量
int ty[] = {1, 0, -1, 0}; // y 方向的偏移量
while (!q.empty()) {
vector<int> current = q.top();
q.pop();
int w = -current[0];
int x = current[1];
int y = current[2];
if (vis[x][y]) continue;
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int xx = x + tx[i];
int yy = y + ty[i];
int ww = 0;
if (0 <= xx && xx < n && 0 <= yy && yy < m && mp[xx][yy] != 0 && !vis[xx][yy] && mp[xx][yy] <= w) {
if (mp[xx][yy] == -1) {
ww = 100;
} else {
ww = w - mp[xx][yy];
}
if (ww > dis[xx][yy]) {
dis[xx][yy] = ww;
q.push({-ww, xx, yy});
}
}
}
}
return vis[n - 1][m - 1];
}
int main() {
int n, m;
scanf("%d,%d", &n, &m); // 读取矩阵的行数和列数
vector<vector<int>> mp(n, vector<int>(m)); // 存储矩阵的二维数组
// 读取矩阵的每一个元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d,", &mp[i][j]);
}
}
int L = 0;
int R = 100;
int ans = -1;
// 二分查找
while (L <= R) {
int mid = (L + R) / 2;
if (check(mid, n, m, mp)) {
ans = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
cout << ans << endl; // 输出结果
return 0;
}
Python
import heapq # 导入heapq模块,用于优先队列实现
# 读取输入的n和m,它们是由逗号分隔的整数
n, m = map(int, input().split(','))
# 读取二维列表mp,其中包含n行m列的整数,元素由逗号分隔
mp = [list(map(int, input().split(','))) for i in range(n)]
L, R = 0, 100 # 初始化L为0,R为100
ans = -1 # 初始化变量ans为-1
# 定义一个名为check的函数,它接受参数mid
def check(mid):
# 初始化一个n行m列的二维列表dis,所有元素初始化为-1
dis = [[-1] * m for i in range(n)]
# 初始化一个n行m列的二维列表vis,所有元素初始化为False
vis = [[False] * m for i in range(n)]
# 根据mid和mp[0][0]的值计算dis[0][0]的初始值
dis[0][0] = mid - mp[0][0]
# 处理mp[0][0]的特殊情况
if mp[0][0] == -1:
dis[0][0] = 100
elif mp[0][0] == 0 or dis[0][0] < 0:
return False # 如果条件不满足,则返回False
q = [] # 初始化一个空列表q
heapq.heappush(q, [-dis[0][0], 0, 0]) # 将初始值推入优先队列q
tx = [0, 1, 0, -1] # 定义x方向的可能移动
ty = [1, 0, -1, 0] # 定义y方向的可能移动
while len(q) != 0: # 循环直到优先队列q为空
w, x, y = heapq.heappop(q) # 从优先队列q中弹出具有最小w值的元素
w = -w # 获取w的实际值
if vis[x][y]: # 检查当前位置(x, y)是否已被访问
continue # 跳过循环的剩余部分,继续下一次迭代
vis[x][y] = True # 标记当前位置(x, y)为已访问
for i in range(4): # 遍历可能的移动方向
xx, yy, ww = x + tx[i], y + ty[i], 0 # 计算新的位置,并初始化ww
if 0 <= xx < n and 0 <= yy < m and mp[xx][yy] != 0 and not vis[xx][yy] and mp[xx][yy] <= w:
# 检查新位置是否有效且未被访问,且其值在限制内
if mp[xx][yy] == -1:
ww = 100 # 对特殊情况更新ww为100
else:
ww = w - mp[xx][yy] # 根据当前值和mp[xx][yy]更新ww
if ww > dis[xx][yy]: # 检查ww是否大于dis中的当前值
dis[xx][yy] = ww # 使用ww更新dis中的值
heapq.heappush(q, [-ww, xx, yy]) # 将新值推入优先队列q
return vis[n - 1][m - 1] # 返回访问数组中右下角的值
# 使用二分查找来找到满足check函数的最佳值
while L <= R: # 循环直到L小于或等于R
mid = (L + R) // 2 # 计算中间值
if check(mid): # 使用中间值调用check函数,并检查结果
ans = mid # 如果check函数返回True,则更新ans的值
R = mid - 1 # 更新R以进行下一次迭代
else:
L = mid + 1 # 更新L以进行下一次迭代
print(ans) # 打印最终的答案
题目描述
有一辆汽车需要从 m * n的地图的左上角(起点)开往地图的右下角(终点 ),去往每一个地区都需要消耗一定的油量,加油站可进行加油
请你计算汽车确保从起点到达终点时所需的最少初始油量
说明:
(1)智能汽车可以上下左右四个方向移动
(2)地图上的数字取值是 0 或 −1 或者正整数:
−1:表示加油站,可以加满油,汽车的油箱容量最大为 100;
0 :表示这个地区是障碍物,汽车不能通过
正整数:表示汽车走过这个地区的耗油量
(3)如果汽车无论如何都无法到达终点,则返回 −1
输入描述
第一行为两个数字,M , N,表示地图的大小为 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
说明:无论如何都无法到达终点