思路：二分答案+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 \le 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

说明：无论如何都无法到达终点