Problem G: 机器人路径5*
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:11
Solved:3
Description
一个机器人位于一个 m x n 方格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图到达方格的右下角(在下图中标记为“Finish”)。
这次小明的机器人又迎来了新的挑战,网格中设置了泥坑。下图中每个单元格包含一个能量值 energy[i][j]。
- 如果 energy[i][j] >= 0,机器人可以获得该单元格的能量。
- 如果 energy[i][j] < 0,机器人会遇到一个泥坑,走出这个泥坑机器人将会消耗掉该单元格绝对值的能量。
返回机器人到达“Finish”路径上可以获得的最大能量数 。注意:机器人的能量值是可以为负数的。
下面图示依样例数据,使用了两块浮垫获得最大能量数为:1+2+0+6+9+0+5=23 . 其路径用蓝色线条标注。
Input
第一行两个整数 m 与 n (m表示行,n表示列) 。下面 m 行每行 n 个整数 energy[i],[j]。
Output
返回机器人在路径上可以获得的最大能量数 。注意:机器人的能量值是可以为负数的。
Sample Input Copy
3 5
1 2 -3 4 -5
2 -4 6 2 6
3 2 9 -6 5
Sample Output Copy
23
HINT
-
1<=n,m<=500
-
-1000 <= energy[i][j] <= 1000