同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

10000_走下去

2022-5-16 18:16| 发布者: Hocassian| 查看: 90| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504326893400-Problem List-采集的数据-后羿采集器.html

Pro.ID

10000

Title

走下去

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10000

AC

Submit

144

Ratio

25.00%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

设有N×N的方格图( N ≤ 500 )，在其中的某些方格中放入正整数，而其他的方格中则放入数字0。如下图所示：

A
0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
B

某人从图的左上角的A点出发，只可以向下或向右行走，直到到达右下角的B点。在走过的路上，他取走方格中的数（取走后的方格中将变为数字0）。这人从A点走到B点，可以得到的最大数和是多少。

输入

多测试用例。

每个测试用例的第一行是一个正整数 n ;

接下来是n行每行n个数组成的矩阵。

输出

Description

设有N×N的方格图( N ≤ 500 )，在其中的某些方格中放入正整数，而其他的方格中则放入数字0。如下图所示：

A
0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
B

Input

多测试用例。

每个测试用例的第一行是一个正整数 n ;

接下来是n行每行n个数组成的矩阵。

Output

每个测试用例输出一行结果：从A点到B点，得到的最大数和。

Sample Input

3
1 2 3
4 5 6
7 8 9

Sample Output

Source

2018菜鸟杯

样例输入