7000 - 学游泳
Time Limit : 1 秒
Memory Limit : 128 MB
小X准备趁着暑假去学游泳。他发现游泳池是n行m列的方格。因为游泳池里的水深浅不一，所以这n×m个方格对于小X的危险系数也会不一样。小X第一次需要从左上角的方格(1,1)出发， 游到右下角的方格(n,m)，小X每次只能从当前方格游到上下左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。小X担心会发生危险，所以希望你帮他找一条危险系数最小的路径。一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。注意：这条路径不能经过同一个方格两次（小X当然不希望去那么危险的地方再游一次）
Input
第一行有两个用空格隔开的正整数n和m，表示泳池的行数和列数
接下来共有n行数据，每行有m个用空格隔开的>=0的整数，表示每个方格的危险系数
Output
一个整数， 表示方格(1,1)游到方格(n,m)的最小的危险系数
Examples
Input
4 5 1 7 2 8 2 3 10 1 5 1 2 8 3 7 1 1 2 1 20 1
Output
19
Hint
数据范围
对于30%的数据，1≤n,m≤5
对于另外40% 的数据，1≤n,m≤20， 每个方格的危险系数=0 或1
对于100%的数据，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
Source
常州市2016“信息与未来”夏令营选拔赛