题面解释:

在一个 $N \times N$ 的迷宫中，配送员从左上角出发，目标是到达右下角。他可以向上下左右四个方向移动，每移动到一个相邻的格子需要 $1$ 个单位时间，且必须在最多 $K$ 个单位时间内到达目的地。每个格子都有一个辐射值，配送员需要穿着防护能力不低于相应辐射值的防护服才能通过该格子。因此，配送员希望知道，所需的最低防护能力是多少，以确保能安全到达目的地并满足时间限制。输入包括两个正整数 $N$ 和 $K$，接下来是一个 $N$ 行的矩阵，表示每个格子的辐射值。输出为一个整数，表示配送员所需的最低防护能力。

在课程前面我们学习了二分答案和二分查找，也学习了单(多)源BFS，这道题目知识点肯定是不难的，只是把两种算法缝合到了一起，在机考中缝合怪也是比较常见的。

思路：二分答案+bfs求最短路

看到输出描述要求输出满足条件的最小值，凡是出现最小，最大，最小的最大，最大的最小我们都可以往二分方面去想一想是否有二分性

性质:可以发现，防护值越大，越容易通过更多的位置，最短路越短。反之最短路越长(换一句话说当防护值为x的时候能通过右下角，那么防护值x+1肯定能通过右下角,如果(x+1)都不能，那么x肯定也不能到达)。因此是满足二分性的，所以我们可以二分这个防护值，得到一个最小的防护值使得最短路 <= k.

做法：首先确定防护力的最小和最大可能值。使用二分查找在这个范围内寻找最小的防护力。对于每一个中间值，利用广度优先搜索（单源BFS）从左上角出发，只有通过辐射值不超过当前中值的格子，并计算移动步数是否不超过K。如果可以到达终点，则尝试更小的防护力；否则，增加防护力。最终找到满足条件的最小防护力值。

具体步骤如下：

1. 要使用二分答案那首先确定二分数据范围：

   • 防护能力的最小值为左上角和右下角的辐射值中的较大者。
   • 防护能力的最大值为迷宫中所有格子辐射值的最大值。

2. 二分查找：

   • 在上述范围内进行二分查找，选择中间值 mid 作为当前的防护能力。
   • 使用广度优先搜索（BFS）从左上角开始，检查能否在 $K$ 步内到达右下角，并且所经过的每个格子的辐射值都不超过 mid。经过前面4题的学习这个单源BFS太过于轻松。

3. 判断能否到达：

   • 如果 BFS 返回 true，说明在当前防护能力下可以到达终点，则尝试更小的防护能力。
   • 如果 BFS 返回 false，说明当前防护能力不足，增加防护能力。

4. 结束条件：

   • 最终找到的 answer 即为所需的最低防护能力。

代码

java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    static int n, k;
    static int[][] a;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取n和k
        n = Integer.parseInt(br.readLine().trim());
        k = Integer.parseInt(br.readLine().trim());
        a = new int[n][n];
        // 读取迷宫的辐射值
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().trim().split("\\s+");
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(parts[j]);
            }
        }

        // 二分查找的初始边界
        int left = Math.max(a[0][0], a[n-1][n-1]);
        int right = Integer.MIN_VALUE;
        for (int[] row : a) {
            for (int val : row) {
                if (val > right) right = val;
            }
        }

        int answer = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (bfs(mid)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

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

    // BFS函数，检查是否可以在k步内到达终点，且所有经过的格子辐射值 ≤ val
    private static boolean bfs(int val) {
        // 检查起点和终点的辐射值是否符合
        if (a[0][0] > val || a[n-1][n-1] > val) return false;

        // 定义移动方向：右、左、下、上
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        // 距离数组，记录每个格子的最短步数
        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        dist[0][0] = 0;

        // 使用队列进行BFS
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int steps = dist[x][y];

            // 如果到达终点，检查步数是否 ≤ K
            if (x == n-1 && y == n-1) {
                return steps <= k;
            }

            // 遍历四个方向
            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 >= n) continue;
                // 检查辐射值和是否已访问
                if (a[nx][ny] > val || dist[nx][ny] != -1) continue;
                // 检查步数是否超过K
                if (steps + 1 > k) continue;
                // 更新步数并加入队列
                dist[nx][ny] = steps + 1;
                queue.offer(new int[]{nx, ny});
            }
        }

        // 如果无法到达终点
        return false;
    }
}

python

from collections import deque

# 读取迷宫大小n和最大允许步数k
n = int(input())
k = int(input())

# 读取迷宫的辐射值矩阵a
a = [list(map(int, input().split())) for _ in range(n)]

def bfs(val):
    """
    广度优先搜索函数，检查是否可以在k步内从起点到达终点，
    且所有经过的格子的辐射值不超过val。
    """
    # 如果起点或终点的辐射值超过val，无法通过
    if a[0][0] > val or a[n-1][n-1] > val:
        return False
    
    # 初始化访问矩阵，记录是否访问过
    visited = [[False]*n for _ in range(n)]
    # 使用deque作为队列，存储当前坐标和步数
    q = deque([(0, 0, 0)])  # (x, y, steps)
    visited[0][0] = True  # 标记起点已访问
    
    # 定义四个可能的移动方向：右、下、左、上
    directions = [(0,1),(1,0),(0,-1),(-1,0)]
    
    while q:
        x, y, steps = q.popleft()  # 取出队首元素
        # 如果到达终点，检查步数是否在允许范围内
        if x == n-1 and y == n-1:
            return steps <= k
        # 遍历所有可能的移动方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy  # 计算新坐标
            # 检查新坐标是否在迷宫范围内
            if 0 <= nx < n and 0 <= ny < n:
                # 检查新位置的辐射值是否不超过val，且未被访问过
                if not visited[nx][ny] and a[nx][ny] <= val:
                    # 检查步数是否不会超过k
                    if steps + 1 > k:
                        continue
                    visited[nx][ny] = True  # 标记为已访问
                    q.append((nx, ny, steps + 1))  # 将新位置加入队列
    # 如果无法到达终点
    return False

# 确定二分查找的初始边界
left = max(a[0][0], a[n-1][n-1])  # 防护力的最低可能值
right = max(max(row) for row in a)  # 防护力的最高可能值

# 二分查找寻找最小的满足条件的防护力
while left <= right:
    mid = (left + right) // 2  # 取中间值作为当前防护力
    if bfs(mid):
        right = mid - 1  # 尝试更小的防护力
    else:
        left = mid + 1  # 增加防护力

# 输出最终结果
print(left)

cpp

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

int n, k;  // n: 迷宫大小，k: 最大步数
int a[100][100];  // 存储迷宫中每个格子的辐射值

// BFS函数，检查是否可以在k步内到达终点，且所有经过的格子辐射值 ≤ val
bool bfs(int val) {
    // 检查起点和终点的辐射值是否符合
    if (a[0][0] > val || a[n-1][n-1] > val) return false;

    // 定义移动方向：右、左、下、上
    int dx[4] = {0, 0, 1, -1};  // x方向的变化
    int dy[4] = {1, -1, 0, 0};  // y方向的变化

    // 距离数组，记录每个格子的最短步数
    vector<vector<int>> dist(n, vector<int>(n, -1));  // 初始化为-1，表示未访问
    dist[0][0] = 0;  // 起点的步数为0

    // 使用队列进行BFS，存储x, y坐标
    queue<pair<int, int>> q;
    q.push({0, 0});  // 将起点入队

    while (!q.empty()) {
        pair<int, int> current = q.front(); q.pop();  // 获取队首元素
        int x = current.first;  // 当前x坐标
        int y = current.second;  // 当前y坐标
        int steps = dist[x][y];  // 当前步数

        // 如果到达终点，检查步数是否 ≤ K
        if (x == n-1 && y == n-1) {
            return steps <= k;  // 若步数小于等于K，返回true
        }

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];  // 计算新x坐标
            int ny = y + dy[i];  // 计算新y坐标
            // 检查边界
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;  // 超出边界则跳过
            // 检查辐射值和是否已访问
            if (a[nx][ny] > val || dist[nx][ny] != -1) continue;  // 辐射值超标或已访问则跳过
            // 检查步数是否超过K
            if (steps + 1 > k) continue;  // 若步数超过K，则跳过
            // 更新步数并加入队列
            dist[nx][ny] = steps + 1;  // 更新当前格子的步数
            q.push({nx, ny});  // 将新位置入队
        }
    }

    // 如果无法到达终点
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 读取n和k
    cin >> n >> k;
    // 读取迷宫的辐射值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];  // 输入辐射值
        }
    }

    // 二分查找的初始边界
    int left = max(a[0][0], a[n-1][n-1]);  // 最小防护能力
    int right = INT32_MIN;  // 最大防护能力
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            right = max(right, a[i][j]);  // 找到迷宫中辐射值的最大值
        }
    }

    int answer = right;  // 初始化答案为最大辐射值
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 中间值
        if (bfs(mid)) {  // 如果可以到达终点
            answer = mid;  // 更新答案为当前mid
            right = mid - 1;  // 尝试更小的防护能力
        } else {
            left = mid + 1;  // 增加防护能力
        }
    }

    // 输出结果
    cout << answer;  // 输出最低防护能力
    return 0;
}

本题为2024年9月19日华为机考原题

华为机考的介绍点击这里

题目内容

有一个$N×N$大小的迷宫。初始状态下，配送员位于迷宫的左上角，他希望前往迷宫的右下角。配送员只能沿着上下左右四个方向移动，从每个格子移动到相邻格子所需要的时间是$1$个单位，他必须用最多$K$个(也可以少于$K$个)单位时间到达右下角格子。迷宫的每个格子都有辐射值，配送员必须穿着防护能力不低于相应辐射值的防护服，才能通过该格子。他希望知道，防护服的防护能力最少要达到多少，他才能顺利完成任务。注意:配送员需要通过迷宫的左上角和右下角，因此防护服的防护能力必须大于等于这两个格子的辐射值。

输入描述

前两行各包含一个正整数，分别对应$N$和$K$。 后$N$行各包含$N$整数，以空格分隔，表示地图上每个位置的辐射值。 $2≤N≤100。K≥2N-2$，以保证题目有解。所有辐射值 都是非负整数，绝对值不超过 $10^4$。

输出描述

一个整数，表示配送员穿着防护服的最低防护能力。

样例1

输入

2
2
1 3
2 1

输出

2

说明

配送员可以选择通过左下角(辐射值为2)的路线，耗费2单位时间。

样例2

输入

5
12
0 0 0 0 0
9 9 3 9 0
0 0 0 0 0
0 9 5 9 9
0 0 0 0 0

输出

3

说明

最优路线:往右$2$格，往下$2$格，往左$2$格，往下$2$格，往右$4$格，耗费$12$单位时间，经过格子的最大辐射值为$3$。 另外，在地图不变的情况下，如果$K=16$，输出为$0$；如果K=$8$，输出为$5$。