最新华为OD机试真题-K小姐的网络信号质量评估(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

K小姐的网络信号质量评估(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

✨ K小姐的网络信号质量评估

问题描述

K小姐是一位网络工程师,她需要评估一个网络的信号质量。其中一个做法是将网络划分为 行 列的栅格,然后对每个栅格的信号质量进行计算。

在路测的时候,K小姐希望选择一条信号最好的路线(由彼此相连的栅格组成)进行演示。现在给出一个 行 列的整数矩阵 ,其中每个单元格的数值 表示该栅格的信号质量(已归一化,无单位,值越大信号越好)。

要求K小姐从左上角 $$ 出发,到达右下角 ,设计一条最优路测路线。请你帮助K小姐计算该路线的得分。

规则如下:

1. 路测路线每次只能往上、下、左、右四个方向移动,不能对角移动。
2. 路线的评分以路线上信号最差的栅格为准。例如路径 的得分为 ,因为该路线上信号最差的栅格的信号质量为 。路线最优表示该条路线的评分最高。

输入格式

第一行包含一个正整数 表示栅格的行数。

第二行包含一个正整数 表示栅格的列数。

接下来 行,每行包含 个整数,表示栅格地图每一行的信号值,其中每个单元格的数值为 。

• 
• 

输出格式

输出一个整数,表示最优路线的得分。

样例输入

3 
3
5 4 5
1 2 6
7 4 6

样例输出

4

样例解释

最优路线为: ,该路线上信号最差的栅格信号质量为 ,因此得分为 。

样例输入

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

样例解释

最优路线为: ,该路线上信号最差的栅格信号质量为 ,因此得分为 。

数据范围

• 
• 

题解

本题可以使用二分答案+DFS的方法来解决。

首先,我们可以确定答案的范围在 之间。然后,我们可以对答案进行二分,判断当前的答案是否可行。

对于每个答案 ,我们从起点开始进行DFS。在DFS的过程中,如果当前栅格的信号质量小于 ,则直接返回 。如果当前栅格的信号质量大于等于 ,则继续向四个方向进行DFS。如果能够到达终点 ,则说明当前的 是可行的,我们可以尝试更大的 。如果无法到达终点,则说明当前的 太大了,我们需要缩小 的范围。

通过二分答案,我们可以找到最大的 ,使得从起点到终点存在一条路径,该路径上的所有栅格的信号质量都大于等于 。这个 就是最优路线的得分。

时间复杂度: ,其中 和 分别为栅格的行数和列数, 为信号质量的最大值。 空间复杂度: ,用于存储访问数组。

参考代码

• Python

import sys
sys.setrecursionlimit(10**6)
def dfs(x, y, limit, g, vis, dx, dy, n, m):
    if g[x][y] < limit:
        return False
    if x == n - 1 and y == m - 1:
        return True
    vis[x][y] = True
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and g[nx][ny] >= limit:
            if dfs(nx, ny, limit, g, vis, dx, dy, n, m):
                return True
    return False

def main():
    n, m = [int(input()) for _ in range(2)]
    g = [list(map(int, input().split())) for _ in range(n)]
    vis = [[False] * m for _ in range(n)]
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]

    left, right = 1, 65535
    while left < right:
        mid = (left + right + 1) // 2
        for i in range(n):