题目描述
网络信号经过传递会逐层衰减，且遇到阻隔物无法直接穿透，在此情况下需要计算某个位置的网络信号值。注意:网络信号可以绕过阻隔物
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
例如
代码语言：javascript复制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。
一个网格如果可以途径不同的传播衰减路径传达，取较大的值作为其信号值。
示例一
输入
代码语言：javascript复制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
输出
代码语言：javascript复制2
示例二
输入
代码语言：javascript复制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
输出
代码语言：javascript复制0
备注
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开始递增。
代码
代码语言：javascript复制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])
时空复杂度
时间复杂度：O(MN)。需要遍历整个grid二维数组。
空间复杂度：O(1)。无需checkList，不考虑grid二维数组所占空间，仅需若干常数变量。
