华为OD统一考试 - 寻找最优的路测线路

题目描述

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

路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。

现给出 R 行 C 列的整数数组 Cov，每个单元格的数值 S 即为该栅格的信号质量（已归一化，无单位，值越大信号越好）。

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

规则：

1. 路测路线可以上下左右四个方向，不能对角
2. 路线的评分是以路线上信号最差的栅格为准的，例如路径 8→4→5→9 的值为4，该线路评分为4。线路最优表示该条线路的评分最高。

输入描述

第一行表示栅格的行数 R

第二行表示栅格的列数 C

第三行开始，每一行表示栅格地图一行的信号值，如5 4 5

输出描述

最优路线的得分

备注

• 1 ≤ R，C ≤ 20
• 0 ≤ S ≤ 65535

用例

输入	3 3 5 4 5 1 2 6 7 4 6
输出	4
说明	路线为：5→4→5→6→6

输入	6 5 3 4 6 3 4 0 2 1 1 7 8 8 3 2 7 3 2 4 9 8 4 1 2 0 0 4 6 5 4 3
输出	3
说明	路线为：3→4→6→3→4→7→7→8→9→4→3→8→8→3→4→4→6→5→4→3

题目解析

用例1图示                                  用例2图示

本题需要我们求解 起点(0,0) 到 终点(r-1, c-1) 的所有路径中 "最大的" 最小权值节点的权值。

注：每条路径都由至少一个点组成，而每个点都有权值，因此每条路径自身都有一个最小权值节点。比如路径：5→4→5→6→6，其中最小权值节点的权值就是4

本题需要我们找到起点->终点的所有路径各自的最小权值节点，并比较出其中最大的那个。

下面使用Dijistra算法模拟下用例1的解题过程：

首先，我们需要定义一个dist数组：

• dist[x][y]表示起点(0,0)到终点(x,y)的所有路径中“最大的”最小权值节点的权值

由于dist[x][y]最终记录的是一个最大值，因此我们需要将dist[x][y]初始化为一个最小值，方便后面被更大值替换，由于本题节点（栅格）的权值（信号强度）最小为0，因此这里dist[x][y]可以初始化为0。

初始时，我们将dist数组所有元素都初始化为0，其中dist[0][0] = matrix[0][0]，因为起点(0,0)到终点(0,0)的路径中只有一个节点(0,0)。

之后，我们需要定义一个优先队列pq，pq记录路径的终点（x,y），各路径终点的优先级为：对应路径"最大的"最小权值节点的权值，即dist[x][y]，即dist[x][y]越大，则对应路径终点(x,y)在优先队列中的优先级越高。

初始时，将(0,0)加入优先队列。

下面开始从优先队列不停取出优先级最高的节点：

每当从优先队列中取出一个路径终点（优先级最高），则可以获得如下信息：

• 路径终点的位置 (ux, uy)
• 路径的最小权值节点的权值：dist[ux][uy]

之后基于(ux, uy) 向上下左右四个方向探索，如果新位置(vx, vy)不越界，则进入新位置：

• 此时路径终点从(ux, uy)变更为(vx, vy)
• 此时路径的最小权值节点的权值w为：min(dist[ux][uy], matrix[vx][vy])

我们得到了一个新的路径，新路径的终点为(vx, vy)，新路径中最小权值节点的权值w为 min(dist[ux][uy], matrix[vx][vy])

另外，如果 w > dist[vx][vy]，则说明我们找到了起点(0,0)到(vx, vy)的更优路径，即找到了更大的最小权值节点，因此需要更新 dist[vx][vy] = w，然后将新路径加入到pq中重新排优先级。

按此逻辑一直进行，直到pq为空时，我们就找完了起点(0,0)到所有节点的路径的"最大的"最小权值节点的权值。

最后返回 dist[r-1][c-1] 记录的 起点(0,0) 到 (r