Problem1074--矩阵取数Ⅱ

1074: 矩阵取数Ⅱ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 490  Solved: 247
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI想要大家了解基本的动态规划,所以它不知道从哪弄来了一个n*m的矩阵,矩阵每个元素是一个整数,你现在在左上角(第一行第一列),每次只能朝右或者下走到相邻的位置,不能走出矩阵。走过的数的总和作为你的得分。现在PIPI想知道它去每一个格子的最大得分是多少?
怎么样,是不是依然很简单呢?

Input

多组输入。 
第一行为两个整数n,m(1<=n,m<=500) 
接下来n行,每行m个数字,每个数字都在int范围内。( ̄▽ ̄)" 

Output

对于每组数据,输出一个n*m的矩阵。

Sample Input

3 4
1 2 3 4 
1 2 8 2
1 1 1 1

Sample Output

1 3 6 10
2 5 14 16
3 6 15 17

Source/Category