#673. 采花生
-
ID: 673
传统题
1000ms
128MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
采花生
Description
在参加“采花生” 这个项目比赛时， 考官会出示一块 n 行、 m 列的花生田，上面一共种了 n*m 株花生苗。 每株花生植株下都结了一定数量的花生果， 比赛开始时选手站在第 1 行， 第 1 列的位置， 现要求用最短的时间找到结花生果最多的一株花生植株（数据保证花生果最多的植株只有一株） ， 然后按先向南（下）走， 再向东（右） 的路线顺序去采摘它的花生果， 沿路经过的其他花生植株下面的花生果也要一并采摘下来， 但不允许采摘没有路过的花生植株， 否则依犯规出局处理。 问这个选手一共可以采摘到多少粒花生果？如一块 n=5， m=6 的花生田
可以发现结花生果最多的那株花生植株在（4， 5）， 则选手采摘的顺序应为（1， 1） -（2， 1） -（3， 1） -（4， 1） -（4， 2） -（4， 3） -（4， 4） -（4， 5），一共采得的花生果粒数为 5+9+10+4+6+9+18+25=86。
Input Format
第 1 行有两个整数 n 和 m( 1 < n,m <= 100 )， 表示花生田一共有 n 行 m 列。第 2 至 n+1 行， 每行有 m 个用空格隔开的整数， 第 i + 1 行的第 j 个整数 Pij（0 <= Pij <= 700） 表示花生田里植株(i, j)下花生的数目， 0 表示该植株下没有花生。
Output Format
只有一行， 一个整数， 表示选手一共摘到的花生果数目。5 6
5 7 4 5 1 13
9 6 3 2 8 7
10 14 0 1 9 4
4 6 9 18 25 0
3 1 2 9 0 286