大家好，我是吴师兄，关注我，每天更新大厂最新笔试题解析。
题目描述
在PCB印刷电路板设计中，器件之间的连线，要避免线路的阻抗值增大，而且器件之间还有别的器任和别的干扰源，在布线时我们希望受到的干扰尽量小。
现将电路板简化成一个M × N的矩阵，每个位置（单元格）的值表示其源干扰度。
如果单元格的值为0，表示此位置没有干扰源，如果单元格的值为非0，则表示此位置是干扰源，其值为源干扰度。连线经过干扰源或干扰源附近会增加连线的总干扰度。
位置A[x,y]的干扰源的源干扰广为d (d>0)，则连线的干扰度计算如下：
1、若连线经过位置A[x,y]，则其总开扰广会增加加
2、若连线经过离位置A[x,y]距离小于d的位置时，设其距离为k，则总干扰度会增加(d-k)
3、若连线经过离位置A[x,y]距离大于或等于d的位置时，总干扰都不会增加；
注：位置[x1,y1]和位置[x2,y2]之间距离的定义为：|x1-x2| |y1-y2|。
如下3x3矩阵，位置[1,1]的源干扰度是2，连线的位置序列为：[0,0]->[0,1]->[0,2]->[1,2]->[2,2]。
暂时无法在飞书文档外展示此内容
其中[0,1]和[1,0]到干扰源的距离为1，会叠加1的干扰度；其他位置到[1,1]的距离均大于等于2，所以不会叠加干扰度。因此这条连线的总干扰度为2。
现在我们需要将左上角的器件到右下角的器件进行连线，两个器件的位置分别是左上角的[0,0]和右下角的[M-1,N-1]。由于我们希望连线尽量地短，从位置[0,0]到[M-1,N-1]的连线途中，我们规定连线只能向下或向右。
请根据输入(M × N的矩阵)，计算出连线的最小干扰度。
输入描述
第一行是两个整数M和N(M和N最大值为1000)，表示行数和列数；
接着是M行的数据，每一包含N个整数，代表每个位置的源干扰度，每个源干扰度小于50。
输出描述
左上角[0,0]到右下角[M-1,N-1]连线的最小总干扰度。
示例一
输入
代码语言：javascript复制3 3
0 0 0
0 2 0
0 0 0
输出
代码语言：javascript复制2
说明
其中一条可以使干扰度最小的路径为：[0,0]->[0,1]->[0,2]->[1,2]->[2,2]，其干扰度为2。
示例二
输入
代码语言：javascript复制5 5
0 0 0 0 0
0 0 2 0 0
0 2 0 2 0
0 0 0 0 0
0 0 0 0 0
输出
代码语言：javascript复制1
说明
先从[0,0]往下走到最下面[4,0]，再往石走到右下角[4,4]，途径[2,0]时叠加一个干扰度。
示例三
输入
代码语言：javascript复制5 5
0 0 0 0 0
0 0 2 0 0
0 2 0 2 0
0 0 2 0 0
0 0 0 0 0
输出
代码语言：javascript复制2
时空限制
时间限制： C/C 2000MS，其他语言4000MS
内存限制： C/C 256MB，其他语言512MB
解题思路
本题属于综合性较强的题目，结合了BFS和DP两个知识点。
首先我们需要根据原矩阵，构建出每一个位置干扰值叠加的结果，得到一个新的矩阵grid_new。这里显然就是一个基于BFS计算层数的问题。
暂时无法在飞书文档外展示此内容
在得到新的矩阵grid_new之后，问题就转变为，对grid_new构建一条从左上到右下的路径，每次只能够向右或向下移动，路径经过的点的总和需要最小。这是一个经典的路径DP问题，和LeetCode64、最小路径和完全一致。
代码
代码语言：javascript复制# 华为OD算法训练营咨询微信：od1336
from collections import deque
DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# 对于grid中每一个干扰源，以干扰源作为起点进行BFS，更新grid_new
def BFS_update_grid_new(val, grid_new, i, j, m, n):
check_list = [[0] * n for _ in range(m)]
check_list[i][j] = 1
grid_new[i][j] = val
q = deque()
q.append((i, j))
# 注意这里退出循环的条件和val相关
while val > 1:
val -= 1
qSize = len(q)
for _ in range(qSize):
cur_x, cur_y = q.popleft()
for dx, dy in DIRECTIONS:
nxt_x, nxt_y = cur_x dx, cur_y dy
if 0 <= nxt_x < m and 0 <= nxt_y < n and check_list[nxt_x][nxt_y] == 0:
q.append((nxt_x, nxt_y))
grid_new[nxt_x][nxt_y] = val
check_list[nxt_x][nxt_y] = 1
# 用于解决最小路径和问题的函数
def find_min_sum_path(grid_new, m, n):
# 构建大小为m*n的dp数组，dp[i][j]表示
# 到达grid_new中的点(i,j)，所需的最小路径和
dp = [[0] * (n) for _ in range(m)]
# 初始化(0,0)位置
dp[0][0] = grid_new[0][0]
# 初始化dp数组第0行，只能从左边向右转移得到
for j in range(1, n):
dp[0][j] = dp[0][j-1] grid_new[0][j]
# 初始化dp数组第0列，只能从上边向下转移得到
for i in range(1, m):
dp[i][0] = dp[i-1][0] grid_new[i][0]
# 遍历剩余所有点
# 点(i,j)的状态，只能从点(i-1,j)向下或者从点(i,j-1)向右转移得到
# 故动态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) grid_new[i][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) grid_new[i][j]
return dp[-1][-1]
# 输入行数m，列数n
m, n = map(int, input().split())
# 构建原干扰值矩阵
grid = list()
for _ in range(m):
grid.append(list(map(int, input().split())))
# 初始化干扰值叠加后的新矩阵gird_new
grid_new = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
# 对于每一个干扰源，使用BFS更新grid_new
if grid[i][j] != 0:
val = grid[i][j]
BFS_update_grid_new(val, grid_new, i, j, m, n)
# 调用函数find_min_sum_path，输出答案
print(find_min_sum_path(grid_new, m, n))
时空复杂度
时间复杂度：O(MNk)。其中k为干扰源的数目，一共需要进行k次BFS，每次BFS的时间复杂度为O(MN)。另外，DP过程的时间复杂度为O(MN)。
空间复杂度：O(MN)。grid_new、check_list、dp等二维矩阵所占空间均为O(MN)。
