Problem B: 机器人路径3
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:25
Solved:12
Description
一个机器人位于一个 m x n 方格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图到达方格的右下角(在下图中标记为“Finish”)。
已知每个方格(i,j)的权值 a[i][j] 。最终机器人走到右下角时,将路径上的所有的权值累加起来为路径和,返回所有从起点到右下角路径中最小的路径和。
如下样例数据,路径为(1,1) >(1,2) >(1,3) >(2,3)>(2,4) >(3,4) >(3,5) ,获得最小的路径和为 :2+5+3+3+4+2+6=25。
Input
第一行两个整数 n,m。下面 n 行每行 m 个整数 a[i],[j]。
Output
一个整数表示机器人找到从从(1,1) 出发到 (n,m) 的最小值。
Sample Input Copy
3 4
1 1 2 3
2 4 3 5
3 7 6 1
Sample Output Copy
13
HINT
保证行列数均小于等于2000。1<= a[i][j]<10000。