华为2023秋招笔试真题解析

五分钟学算法

发布于 2023-09-20 08:58:43

4470

发布于 2023-09-20 08:58:43

文章被收录于专栏：五分钟学算法

题目描述

网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物

array[m][n] 的二维数组代表网格地图，
array[i][j] = 0 代表 i 行 j 列是空旷位置;
array[i][j] = x (x 为正整数)代表 i 行 j 列是信号源，信号强度是 x;
array[i][j] = -1 代表 i 行 j 列是阻隔物.
信号源只有 1 个，阻隔物可能有 0 个或 多 个
网络信号衰减是上下左右相邻的网格衰减 1
现要求输出对应位置的网络信号值。

输入

输入为三行：

第一行为 m、n，代表输入是一个 m × n的数组。

第二行是一串 m × n 个用空格分隔的整数。每连续 n 个数代表一行，再往后 n 个代表下一行，以此类推。对应的值代表对应的网格是空矿位置，还是信号源，还是阻隔物。

第三行是 i、j，代表需要计算 array[i][j] 的网络信号值。注意:此处i和j均从 0 开始，即第一行 i为 0

例如

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4

代表如下地图

需要输出第 1 行第 4 列的网络信号值，如下图，值为 2

输出

输出对应位置的网络信号值，如果网络信号未覆盖到，也输出 0。

一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值。

示例一

输入

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
1 4

输出

示例二

输入

6 5
0 0 0 -1 0 0 0 0 0 0 0 0 -1 4 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
2 1

输出

备注

m不一定等于n，m < 100，n < 100 ,网络信号小于 1000 。
信号源只有 1 个，阻隔物可能有 0 个或多个。
输入的 m，n与第二行的数组是合法的，无需处理数量对不上的异常情况。
要求输出信号值的位置，不会是阻隔物。

解题思路

注意，本题和LC994. 腐烂的橘子几乎完全一致，属于计算BFS层数的问题，而且只有一个信号源，所以使用常规的单源BFS方法即可完成。

要注意以下几点：

输入的数据是一个长度为m*n的一维数组，需要转换成我们常用的grid二维矩阵。
本题可以直接在grid上进行元素修改，最终输出要求的点(target_x, target_y)的强度值grid[target_x][target_y]即可。
由于直接对grid进行修改，如果某个点的强度已经从0修改为其他值，说明已经进入过，故无需重复使用checkList进行检查。
搜索层数可以从信号源的强度intensity不断-1来判断，无需从level = 0开始递增。

代码

from collections import deque

# 搜索的四个方向
D = [(0,1), (1,0), (-1,0), (0,-1)]

m, n = map(int, input().split())
lst = list(map(int, input().split()))
target_x, target_y = map(int, input().split())

# 需要把lst转化为常用的grid二维数组
grid = list()
for i in range(0, m*n, n):
    # lst中的每n个元素作为一行，存入grid中
    grid.append(lst[i:i+n])

q = deque()

# 双重循环遍历grid，寻找信号源
for i in range(m):
    for j in range(n):
        # 0表示空地，-1表示阻碍，故grid[i][j]大于0时，点(i,j)是信号源
        if grid[i][j] > 0:
            # 将信号源存入队列q中，作为BFS的起始位置
            q.append((i, j))
            # 获得信号源的强度intensity
            intensity = grid[i][j]
            # 由于有且只有一个信号源，所以找到信号源后直接退出循环
            break

# 注意，本题可以直接在grid数组上进行修改，故无需设置checkList检查数组
# 另外，搜索层数可以根据intensity递减
while len(q) > 0:
    # 本次搜索，强度-1
    intensity -= 1
    # 如果强度降为0，无需进行搜索，直接退出循环
    if intensity == 0:
        break

    # 获得当前队列长度，为本层BFS需要出队的节点数
    qSize = len(q)
    for _ in range(qSize):
        # 弹出当前队头元素点(x, y)
        x, y = q.popleft()
        # 遍历点(x, y)的近邻点
        for dx, dy in D:
            nx, ny = x+dx, y+dy
            # (nx, ny)需要满足：
            # 1. 不越界
            # 2. 在grid中为0
            if (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0):
                # 直接将grid[nx][ny]修改为强度intensity
                # 这一步替代了checkList
                grid[nx][ny] = intensity
                # 并且将点(nx, ny)加入队列中继续进行搜索
                q.append((nx, ny))


# 最后输出grid中点(target_x, target_y)的值即可
print(grid[target_x][target_y])