题目内容

在PCB印刷电路板设计中，器件之间的连线需要避免线路的阻抗值增大、而且赛件之间还有别的器件和别的干扰源，在布线时我们希望受到的干扰尽量小。现将电路板简化成一个M×N的矩阵，每个位置(单元格)的值表示其源干扰度。

如果单元格的值为0，表示此位置没有干扰源;如果单元格的值为非0，则表示此位置是干扰源，其值为源干扰度。连线经过干扰源或干扰源附近会增加连线的总干扰度。位置A[x, y]的干扰源的源干扰度为d(d>0)，则连线的干扰度计算如下：

1、若连线经过位置A[x, y]，则其总干扰度会增加d；

2、若连线经过离位置A[x, y]距离小于d的位置时，设其距离为K，则总干扰度会增加（d-k）;

3、若连线经过离位置A[x,y]距离大于或等于d的位置时，总干扰度不会增加;

位置[x1,y1]和位置[x2,y2]之间距离的定义为:|x1-x2|+|y1-y2|

输入描述

第一行是两个整数M和N（M和N的最大值是1000），表示行数和列数;

接着是M行的数据，每一行包含N个整数，代表每个位置的源干扰度，每个源干扰度小于

输出描述

左上角[0,0]到右下角[M-1,N-1]连线的最小总干扰度。

样例

输入：

3 3
0 0 0
0 2 0
0 0 0
输出：

2

题目解析

1、干扰度累加：

• 对于每个干扰源位置（i,j），其干扰度范围是由该位置的干扰度d决定的。它的影响不仅局限于 (i, j)本身，还会扩展到该位置周围的其他位置，影响范围由 d决定。
• 计算每个位置的干扰度时，我们需要根据其到干扰源的距离来判断是否增加干扰度。