思路：二分答案+DFS

首先，由于路径的优劣是按照路径中经过的最小权值决定的，因此我们可以考虑使用二分查找去缩小边界

我们可以枚举最终的答案$x$，然后使用DFS去查询，是否有一条从起点到终点路径，使得经过的点的权值都$\ge x$，如果有，则说明当前$x$满足条件，可以让二分边界往右收缩，否则，则说明不满足条件，可以让二分边界往左收缩，具体可以参考下面代码，代码的注释很详细。

JavaScript

const N = 25;
let n, m;
const g = new Array(N).fill(0).map(() => new Array(N).fill(0));
const vis = new Array(N).fill(0).map(() => new Array(N).fill(false));
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

// 深度优先搜索函数，判断是否能从起点 (x, y) 到达终点 (n-1, m-1)，
// 限制条件是当前路径上的值不小于 limit
function dfs(x, y, limit) {
    // 如果当前位置的值小于 limit，直接返回 False
    if (g[x][y] < limit) {
        return false;
    }
    // 如果已经到达终点，返回 True
    if (x === n - 1 && y === m - 1) {
        return true;
    }
    // 标记当前位置已经访问
    vis[x][y] = true;
    // 遍历四个方向
    for (let i = 0; i < 4; i++) {
        const a = dx[i] + x;
        const b = dy[i] + y;
        // 判断是否越界、已访问或者值小于 limit，是则继续下一个方向
        if (a < 0 || a >= n || b < 0 || b >= m || vis[a][b] || g[a][b] < limit) {
            continue;
        }
        // 递归调用 dfs，判断是否能从新的位置 (a, b) 到达终点
        if (dfs(a, b, limit)) {
            return true;
        }
    }
    // 若四个方向都无法到达终点，则返回 False
    return false;
}

let l = 0;
let r = 65535;

let lineCount = 0;

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', (line) => {
    if (lineCount === 0) {
        n = parseInt(line);
    } else if (lineCount === 1) {
        m = parseInt(line);
    } else {
        g[lineCount - 2] = line.split(' ').map(Number);
    }
    lineCount++;
}).on('close', () => {
    while (l < r) {
        const mid = Math.floor((l + r + 1) / 2);
        // 初始化 vis 数组
        for (let i = 0; i < N; i++) {
            vis[i].fill(false);
        }
        // 如果可以从起点到达终点，更新 l 为当前限制条件
        if (dfs(0, 0, mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    // 输出结果
    console.log(l);
});

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 25;
    static int n, m;
    static int[][] g = new int[N][N];
    static boolean[][] vis = new boolean[N][N];
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    // 深度优先搜索函数，判断是否能从起点 (x, y) 到达终点 (n-1, m-1)，
    // 限制条件是当前路径上的值不小于 limit
    static boolean dfs(int x, int y, int limit) {
        // 如果当前位置的值小于 limit，直接返回 False
        if (g[x][y] < limit) return false;
        // 如果已经到达终点，返回 True
        if (x == n - 1 && y == m - 1) return true;
        // 标记当前位置已经访问
        vis[x][y] = true;
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x, b = dy[i] + y;
            // 判断是否越界、已访问或者值小于 limit，是则继续下一个方向
            if (a < 0 || a >= n || b < 0 || b >= m || vis[a][b] || g[a][b] < limit) continue;
            // 递归调用 dfs，判断是否能从新的位置 (a, b) 到达终点
            if (dfs(a, b, limit)) return true;
        }
        // 若四个方向都无法到达终点，则返回 False
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        // 读取输入矩阵的值
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = scanner.nextInt();
            }
        }

        int l = 0, r = 65535;
        // 二分搜索
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            // 初始化 vis 数组
            for (int i = 0; i < N; i++) {
                Arrays.fill(vis[i], false);
            }
            // 如果可以从起点到达终点，更新 l 为当前限制条件
            if (dfs(0, 0, mid)) l = mid;
            else r = mid - 1;
        }

        // 输出结果
        System.out.println(l);
    }
}

Python

# 设置最大值 N
N = 25
# 输入行数 n
n = int(input())
# 输入列数 m
m = int(input())

# 初始化地图 g，标记是否访问过 vis
g = [[0] * N for _ in range(N)]
vis = [[False] * N for _ in range(N)]

# 定义上、下、左、右四个方向的偏移量
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 深度优先搜索函数，判断是否能从起点 (x, y) 到达终点 (n-1, m-1)，
# 限制条件是当前路径上的值不小于 limit
def dfs(x, y, limit):
    # 如果当前位置的值小于 limit，直接返回 False
    if g[x][y] < limit:
        return False
    # 如果已经到达终点，返回 True
    if x == n - 1 and y == m - 1:
        return True
    # 标记当前位置已经访问
    vis[x][y] = True
    # 遍历四个方向
    for i in range(4):
        a, b = dx[i] + x, dy[i] + y
        # 判断是否越界、已访问或者值小于 limit，是则继续下一个方向
        if a < 0 or a >= n or b < 0 or b >= m or vis[a][b] or g[a][b] < limit:
            continue
        # 递归调用 dfs，判断是否能从新的位置 (a, b) 到达终点
        if dfs(a, b, limit):
            return True
    # 若四个方向都无法到达终点，则返回 False
    return False

# 读取地图输入
for i in range(n):
    g[i] = list(map(int, input().split()))

# 二分查找限制条件的最大值，从 0 到 65535
l, r = 0, 65535
while l < r:
    mid = (l + r + 1) // 2
    # 初始化 vis 数组
    for i in range(N):
        vis[i] = [False] * N
    # 如果可以从起点到达终点，更新 l 为当前限制条件
    if dfs(0, 0, mid):
        l = mid
    else:
        # 否则缩小限制条件的范围
        r = mid - 1

# 输出结果
print(l)

C++

#include<bits/stdc++.h>
using namespace std;

const int N = 25;
int n, m, g[N][N];
bool vis[N][N];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

// 深度优先搜索函数，判断是否能从起点 (x, y) 到达终点 (n-1, m-1)，
// 限制条件是当前路径上的值不小于 limit
bool dfs(int x, int y, int limit) {
    // 如果当前位置的值小于 limit，直接返回 False
    if (g[x][y] < limit) return false;
    // 如果已经到达终点，返回 True
    if (x == n - 1 && y == m - 1) return true;
    // 标记当前位置已经访问
    vis[x][y] = true;
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int a = dx[i] + x, b = dy[i] + y;
        // 判断是否越界、已访问或者值小于 limit，是则继续下一个方向
        if (a < 0 || a >= n || b < 0 || b >= m || vis[a][b] || g[a][b] < limit) continue;
        // 递归调用 dfs，判断是否能从新的位置 (a, b) 到达终点
        if (dfs(a, b, limit)) return true;
    }
    // 若四个方向都无法到达终点，则返回 False
    return false;
}

int main() {
    // 读取输入
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }

    int l = 0, r = 65535;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        // 初始化 vis 数组
        memset(vis, 0, sizeof vis);
        // 如果可以从起点到达终点，更新 l 为当前限制条件
        if (dfs(0, 0, mid)) l = mid;
        else r = mid - 1;
    }

    // 输出结果
    cout << l << endl;
    return 0;
}

题目描述

评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。

路测的时候，希望选择一条信号最好的路线(彼此相连的栅格集合)进行演示。现给出 $R$ 行 $C$ 列的整数数组 $Cov$ ,每个单元格的数值 $S$ 即为该栅格的信号质量(已归一化，无单位,值越大信号越好)。

要求从 $[0, 0]$ 到 $[R-1, C-1]$ 设计一条最优路测路线。返回该路线得分。

规则：

1. 路测路线可以 上下左右四个方向，不能对角。
2. 路线的评分是以路线上信号最差的栅格为准的。例如路径 $8 → 4 → 5 →9$ 的值为 $4$ ，该线路评分为 $4$ 。线路最优表示该条线路的评分最高。

输入描述

第一行表示栅格的行数 $R$；

第二行表示栅格的列数 $C$；

第三行开始，每一行表示栅格地图一行的信号值，每个单元格的数值为 $S$ 。

• $1\le R,C \le 20$
• $1\le S \le 65535$

输出描述

最优路线的得分。

示例1

输入

3
3
5 4 5
1 2 6
7 4 6

输出

4

说明：

路线为： $5 → 4 → 5 →6 →6$ 。

示例2

输入

6
5
3 4 6 3 4
0 2 1 1 7
8 8 3 2 7
3 2 4 9 8
4 1 2 0 0
4 6 5 4 3

输出

3

说明：

路线为： $3 → 4 → 6 → 3 → 4 → 7 → 7 → 8 → 9 → 4 →3 → 8 → 8 → 3 → 4 → 4 → 6 → 5 → 4 → 3$ 。