在一个 N×N 的迷宫中,配送员从左上角出发,目标是到达右下角。他可以向上下左右四个方向移动,每移动到一个相邻的格子需要 1 个单位时间,且必须在最多 K 个单位时间内到达目的地。每个格子都有一个辐射值,配送员需要穿着防护能力不低于相应辐射值的防护服才能通过该格子。因此,配送员希望知道,所需的最低防护能力是多少,以确保能安全到达目的地并满足时间限制。输入包括两个正整数 N 和 K,接下来是一个 N 行的矩阵,表示每个格子的辐射值。输出为一个整数,表示配送员所需的最低防护能力。
在课程前面我们学习了二分答案和二分查找,也学习了单(多)源BFS,这道题目知识点肯定是不难的,只是把两种算法缝合到了一起,在机考中缝合怪也是比较常见的。
看到输出描述要求输出满足条件的最小值,凡是出现最小,最大,最小的最大,最大的最小我们都可以往二分方面去想一想是否有二分性
本题为2024年9月19日华为机考原题
华为机考的介绍点击这里
有一个N×N大小的迷宫。初始状态下,配送员位于迷宫的左上角,他希望前往迷宫的右下角。配送员只能沿着上下左右四个方向移动,从每个格子移动到相邻格子所需要的时间是1个单位,他必须用最多K个(也可以少于K个)单位时间到达右下角格子。迷宫的每个格子都有辐射值,配送员必须穿着防护能力不低于相应辐射值的防护服,才能通过该格子。他希望知道,防护服的防护能力最少要达到多少,他才能顺利完成任务。注意:配送员需要通过迷宫的左上角和右下角,因此防护服的防护能力必须大于等于这两个格子的辐射值。
前两行各包含一个正整数,分别对应N和K。 后N行各包含N整数,以空格分隔,表示地图上每个位置的辐射值。 2≤N≤100。K≥2N−2,以保证题目有解。所有辐射值 都是非负整数,绝对值不超过 104。
一个整数,表示配送员穿着防护服的最低防护能力。
输入
2
2
1 3
2 1
输出
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。