在一个 N×N 的迷宫中,配送员从左上角出发,目标是到达右下角。他可以向上下左右四个方向移动,每移动到一个相邻的格子需要 1 个单位时间,且必须在最多 K 个单位时间内到达目的地。每个格子都有一个辐射值,配送员需要穿着防护能力不低于相应辐射值的防护服才能通过该格子。因此,配送员希望知道,所需的最低防护能力是多少,以确保能安全到达目的地并满足时间限制。输入包括两个正整数 N 和 K,接下来是一个 N 行的矩阵,表示每个格子的辐射值。输出为一个整数,表示配送员所需的最低防护能力。
性质:可以发现,防护值越大,越容易通过更多的位置,最短路越短。反之最短路越长。所以我们可以二分这个防护值,得到一个最小的防护值使得最短路 <= k.
给定一个边长为 N 的正方形迷宫,每个格子都有一个辐射值。配送员从左上角出发,目标是到达右下角。他在迷宫中每次只能向上下左右相邻格子移动,每次移动耗时 1 个单位时间。整个移动过程的总耗时不能超过 K 个单位时间。
配送员位于某个格子时,所穿防护服的防护能力必须不低于该格子的辐射值,否则无法通过该格子。
现在需要确定防护服的最低防护能力,使得在时间限制和辐射限制下,配送员能够顺利穿过迷宫。
约束条件:
开通会员即可查看完整视频题解: 1.题目讲解 2.思路分析 3.逐行代码手写
© CodeFun2000 · 使用条款
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册