E卷-智能驾驶-(200p)

智能驾驶

题目描述

LYA开发了一款智能驾驶系统,可以让汽车在 的地图上从左上角(起点)开往右下角(终点)。地图上的每个位置都有一个数字,表示汽车经过该位置需要消耗的油量。地图上还有一些加油站,汽车经过加油站时可以加满油。

LYA想知道,汽车从起点出发,确保能够到达终点,初始时油箱里至少需要多少油量。

注意:

1. 汽车可以向上、下、左、右四个方向行驶。
2. 地图上的数字含义如下:
   • :表示该位置是加油站,汽车经过时可以将油箱加满,油箱容量为 。
   • :表示该位置是障碍物,汽车无法通过。
   • 正整数:表示汽车经过该位置需要消耗的油量。
3. 如果无论初始油量多少,汽车都无法到达终点,则输出 。

输入格式

第一行包含两个正整数 和 ,表示地图的行数和列数,满足 。

接下来 行,每行包含 个整数,表示地图上每个位置的数字。输入保证加油站的总数不超过 个。

输出格式

输出一个整数,表示汽车从起点出发,确保能够到达终点,初始时油箱里至少需要的油量。

如果无论初始油量多少,汽车都无法到达终点,则输出 。

样例输入

2,2
10,20
30,40

样例输出

70

样例解释

汽车行驶路线为:右 下。

样例输入

4,4
10,30,30,20
30,30,-1,10
0,20,20,40
10,-1,30,40

样例输出

70

样例解释

汽车行驶路线为:右 右 下 下 下 右。

样例输入

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
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40

样例输出

-1

样例解释

无论初始油量多少,汽车都无法到达终点。

数据范围

加油站的总数不超过 个

题解

本题可以使用二分查找和BFS来解决。

首先,我们可以确定初始油量的范围,最小值为 ,最大值为地图上非障碍物位置的油量消耗之和。

然后,我们在这个范围内进行二分查找,每次选择一个中间值作为初始油量,判断以这个初始油量是否能够从起点到达终点。

判断的过程可以使用BFS。从起点开始,将当前位置和剩余油量加入队列。每次从队列中取出一个位置,如果该位置是终点,则说明以当前的初始油量可以到达终点;如果该位置是加油站,则将剩余油量置为油箱容量;否则,将剩余油量减去该位置的油量消耗。然后,将该位置的四个相邻位置加入队列(如果剩余油量足够且未访问过)。如果队列为空,说明无法到达终点。

通过二分查找,我们可以找到最小的初始油量,使得汽车能够从起点到达终点。

参考代码

• Python

import heapq

def check(mid):
    dis = [[-1] * m for _ in range(n)]
    vis = [[False] * m for _ in range(n)]
    dis[0][0] = mid - grid[0][0]
    if grid[0][0] == -1:
        dis[0][0] = 100
    elif grid[0][0] == 0 or dis[0][0] < 0:
        return False
    q = [(-dis[0][0], 0, 0)]
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while q:
        w, x, y = heapq.heappop(q)
        w = -w
        if vis[x][y]:
            continue
        vis[x][y] = True
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != 0 and not vis[nx][ny] and grid[nx][ny] <= w:
                if grid[nx][ny] == -1:
                    nw = 100
                else:
                    nw = w - grid[nx][ny]
                if nw > dis[nx][ny]:
                    dis[nx][ny] = nw
                    heapq.heappush(q, (-nw, nx, ny))
    return vis[n - 1][m - 1]

n, m = map(int, input().split(','))
grid = [list(map(int, input().split(','))) for _ in range(n)]

left, right = 0, 100
ans = -1
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        ans = mid
        right = mid - 1
    else:
        left = mid + 1
print(ans)

• Java

import java.util.*;

public class Main {
    static int n, m;
    static int[][] grid;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nm = sc.nextLine().split(",");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        grid = n