最新华为OD机试真题-K小姐的网络信号质量评估(200分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
✨ K小姐的网络信号质量评估
问题描述
K小姐是一位网络工程师,她需要评估一个网络的信号质量。其中一个做法是将网络划分为 行
列的栅格,然后对每个栅格的信号质量进行计算。
在路测的时候,K小姐希望选择一条信号最好的路线(由彼此相连的栅格组成)进行演示。现在给出一个 行
列的整数矩阵
,其中每个单元格的数值
表示该栅格的信号质量(已归一化,无单位,值越大信号越好)。
要求K小姐从左上角 $$ 出发,到达右下角 ,设计一条最优路测路线。请你帮助K小姐计算该路线的得分。
规则如下:
- 路测路线每次只能往上、下、左、右四个方向移动,不能对角移动。
- 路线的评分以路线上信号最差的栅格为准。例如路径
的得分为
,因为该路线上信号最差的栅格的信号质量为
。路线最优表示该条路线的评分最高。
输入格式
第一行包含一个正整数 表示栅格的行数。
第二行包含一个正整数 表示栅格的列数。
接下来 行,每行包含
个整数,表示栅格地图每一行的信号值,其中每个单元格的数值为
。
输出格式
输出一个整数,表示最优路线的得分。
样例输入
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):
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测