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

华为机考的介绍点击这里

题目内容

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

题面解释:

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

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

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

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