OpenJudge

1050:CZP1608小X学游泳

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
262144kB
描述

暑假快到啦,小X准备趁着这个暑假去学游泳。可是一开始小X就遇到了一个难题。

游泳池划分成了一个n×m的方格,这里n×m表示n行m列。因为游泳池里的水深浅不一,所以这n×m个方格对于小 X 的危险系数也会不一样。

而小X目前需要从左上角的方格(1,1)出发,游到右下角的方格(n,m),小X 次只能从当前方格游到上下左右四个相邻的方格中的某一格,并且在到达终点前不能离开游泳池。

小X很担心会发生什么危险,所以希望你能帮他找一条危险系数最小的路径。

一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。

注意:这条路径不能经过同一个方格两次(小 X 当然不希望去那么危险的地方再游一次)

输入
第一行有两个用空格隔开的正整数n和m 表示泳池的行数和列数。

接下来共有n行数据,每行有m个用空格隔开的大于等于0的整数,表示每个方格的危险系数
输出
输出仅有一行包含一个整数ans, 表示要求的从左上角的方格( 1, 1)出发, 游到右下角的方格( n, m) 的最小的危险系数。
样例输入
4 5
1 7 2 8 2
3 10 1 5 1
2 8 3 7 1
1 2 1 20 1
样例输出
19
提示
【数据范围】

1 ≤n, m ≤ 30, 0 ≤ 每个方格的危险系数 ≤ 100000

【样例解释】

路径: ( 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。

每个题目的视频讲解会逐步推出,请访问
http://i.youku.com/oiclub

全局题号
14437
添加于
2017-04-08
提交次数
29
尝试人数
14
通过人数
8