题解

题目描述

在 PCB 电路板设计中，器件之间的连线需要避免线路的阻抗值增大，而且器件之间还有别的器件和干扰源。在布线时，我们希望受到的干扰尽量小。

电路板简化为一个 M x N 的矩阵，每个位置的值表示其源干扰度。如果位置的值为 0，表示没有干扰源；如果值为 d > 0，表示该位置是一个干扰源，干扰度为 d。

当连线经过位置 (x, y) 时：

1. 如果连线经过该位置，干扰度会增加该位置的源干扰度。
2. 如果连线经过离该位置的距离小于该位置的干扰度，则干扰度会增加 (d - distance)。

题目内容

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

如下$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]连线的最小总干扰度。

样例1

输入

3 3
0 0 0
0 2 0
0 0 0

输出

2

说明

其中一条可以使干扰度最小的路径为:$[0.0]->[0.1]->[0.2]->[1.2]->[2,2]$，其干扰度为$2$

样例2

输入

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 

输出

1

说明

先从$[0.0]$往下走到最下面$[4.0]$，再往右走到右下角$[4,4]$，途径$[2,0]$时叠加了一个干扰度。

样例3

输入

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

说明

先从$[0.0]$往下走到最下面$[4.0]$，再往右走到右下角$[4,4]$，途径$[2,0]$时叠加了一个干扰度。