有一个N×N大小的迷宫。初始状态下,配送员位于迷宫的左上角,他希望前往迷宫的右下角。配送员只能沿着上下左右四个方向移动,从每个格子移动到相邻格子所需要的时间是1个单位,他必须用最多K个(也可以少于K个)单位时间到达右下角格子。迷宫的每个格子都有辐射值,配送员必须穿着防护能力不低于相应辐射值的防护服,才能通过该格子。他希望知道,防护服的防护能力最少要达到多少,他才能顺利完成任务。注意:配送员需要通过迷宫的左上角和右下角,因此防护服的防护能力必须大于等于这两个格子的辐射值。
前两行各包含一个正整数,分别对应N和K。
在一个 N×N 的迷宫中,配送员从左上角出发,目标是到达右下角。他可以向上下左右四个方向移动,每移动到一个相邻的格子需要 1 个单位时间,且必须在最多 K 个单位时间内到达目的地。每个格子都有一个辐射值,配送员需要穿着防护能力不低于相应辐射值的防护服才能通过该格子。因此,配送员希望知道,所需的最低防护能力是多少,以确保能安全到达目的地并满足时间限制。输入包括两个正整数 N 和 K,接下来是一个 N 行的矩阵,表示每个格子的辐射值。输出为一个整数,表示配送员所需的最低防护能力。
性质:可以发现,防护值越大,越容易通过更多的位置,最短路越短。反之最短路越长。所以我们可以二分这个防护值,得到一个最小的防护值使得最短路 <= k.
做法:首先确定防护力的最小和最大可能值。使用二分查找在这个范围内寻找最小的防护力。对于每一个中间值,利用广度优先搜索(BFS)从左上角出发,只有通过辐射值不超过当前中值的格子,并计算移动步数是否不超过K。如果可以到达终点,则尝试更小的防护力;否则,增加防护力。最终找到满足条件的最小防护力值。