← 返回题目
题库练习 方格取数
← 上一题 下一题 →

A716 | 方格取数

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

设有N*N的方格图,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。

某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数。

此人从A点到B 点，试找出一条路径，使得取得的数之和为最大。

输入格式

第一行为两个整数N，M，表示N×N的方格图，M个格子中放有数字。
接下来的每行有三个整数，第一个为行号数x，第二个为列号数y，第三个为在该行、该列上所放的数z。

输出格式

一个整数，表示一条路径上取得的最大的和。

输入输出样例

输入 #1
5 5
1 1 1
2 2 2
3 3 3 
4 4 4
5 5 5
输出 #1
15
C++ 编辑器
输入
输出