题目描述

评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。

路测的时候，希望选择一条信号最好的路线(彼此相连的栅格集合)进行演示。现给出 $R$ 行 $C$ 列的整数数组 $Cov$ ,每个单元格的数值 $S$ 即为该栅格的信号质量(已归一化，无单位,值越大信号越好)。

要求从 $[0, 0]$ 到 $[R-1, C-1]$ 设计一条最优路测路线。返回该路线得分。

思路：二分答案+DFS

首先，由于路径的优劣是按照路径中经过的最小权值决定的，因此我们可以考虑使用二分查找去缩小边界

我们可以枚举最终的答案$x$，然后使用DFS去查询，是否有一条从起点到终点路径，使得经过的点的权值都$\ge x$，如果有，则说明当前$x$满足条件，可以让二分边界往右收缩，否则，则说明不满足条件，可以让二分边界往左收缩，具体可以参考下面代码，代码的注释很详细。

JavaScript