6102: 老周学游泳 II
[Creator : ]
Description
暑假快到啦，老周准备趁着这个暑假去学游泳。可是一开始老周就遇到了一个难题。
游泳池划分成了一个 $n \times m$ 的方格， 表示 $n$ 行 $m$ 列。 因为游泳池里的水深浅不一，所以这 $n \times m$ 个方格对于老周的危险系数也会不一样。
而老周目前需要从左上角的方格 $(1,\ 1)$ 出发， 游到右下角的方格 $(n,\ m)$，老周每次只 能从当前方格游到上下左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。
老周很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。
一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。
注意：这条路径不能经过同一个方格两次（老周当然不希望去那么危险的地方再游一次）。
游泳池划分成了一个 $n \times m$ 的方格， 表示 $n$ 行 $m$ 列。 因为游泳池里的水深浅不一，所以这 $n \times m$ 个方格对于老周的危险系数也会不一样。
而老周目前需要从左上角的方格 $(1,\ 1)$ 出发， 游到右下角的方格 $(n,\ m)$，老周每次只 能从当前方格游到上下左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。
老周很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。
一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。
注意：这条路径不能经过同一个方格两次（老周当然不希望去那么危险的地方再游一次）。
Input
输入数据第一行有两个用空格隔开的正整数 $n,\ m$， 表示泳池的行数和列数。
接下来共有 $n$ 行数据，每行有 $m$ 个用空格隔开的大于等于 $0$ 的整数， 表示每个方格的危险系数。
Output
输出仅有一行包含一个整数 ans， 表示要求的从左上角的方格 $(1,\ 1)$ 出发， 游到右下角的方格 $(n,\ m)$ 的最小的危险系数。
Constraints
对于 $30\%$ 的数据，$1 ≤ n,\ m ≤ 5$
对于另外 $40\%$ 的数据，$1 ≤ n,\ m ≤ 20$， 每个方格的危险系数 = $0$ 或 $1$
对于 $100\%$ 的数据，$1 ≤ n,\ m ≤ 30$，$0 ≤$ 每个方格的危险系数 $≤ 100,000$
Sample 1 Input
4 5
1 7 2 8 2
3 10 1 5 1
2 8 3 7 1
1 2 1 20 1
Sample 1 Output
19
路径： $(1,\ 1) → (1,\ 2) → (1,\ 3) → (2,\ 3) → (2,\ 4) → (2,\ 5) → (3,\ 5) → (4,\ 5)$，
危险系数之和为 $1+7+2+1+5+1+1+1=19$。