5999: 【DP】华为2023秋招-PCB印刷电路板布线

在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。

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

2