问题 1087 --【基础】喜羊羊运动会——采花生

1087: 【基础】喜羊羊运动会——采花生

题目描述

  在参加“采花生”这个项目比赛时,考官会出示一块n行、m列的花生田,一共种了n*m株花生苗。每株花生植株下都结了一定数量的花生果,选手一开始站在第1行,第1列的位置,要求用最短的时间找到结花生果最多的一株花生植株(数据保证花生果最多的植株只有一株),然后按先向南(下)走,再向东(右)的路线顺序去采摘它的花生果,沿路经过的其他花生植株下面的花生果也要一并摘下来,但不允许采摘没有路过的花生植株,否则依犯规出局处理。问这个选手一共可以采摘多少粒花生果? 如一块n=5,m=6的花生田
        第1列  第2列   第3列   第4列    第5列  第6列
第1行     5      7       4       5        1      13
第2行     9      6       3       2        8      7
第3行     10     14      0       1        9      4
第4行     4      6       9       18       25     0
第5行     3      1       2       9        0      2
可以发现结花生果最多的那株花生植株在(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。

输入

第1行:两个整数n m( 1 < n,m <= 100 ),表示花生田一共有n行m列。 第2..n+1行:每行m个空格隔开的整数,第i + 1行的第j个整数Pij(0 <= Pij <= 700)表示花生田里植株(i, j)下花生的数目,0表示该植株下没有花生。

输出

一行,一个整数,表示选手一共摘到的花生果数目。

样例输入输出

输入#1 复制
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 2
输出#1 复制
86

提示

序号 标题 作者 发表时间 费用 订购数 操作