A716. 方格取数
编程题
普及-
知识点
题目描述
设有N*N的方格图,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。
某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数。
此人从A点到B 点，试找出一条路径，使得取得的数之和为最大。
某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数。
此人从A点到B 点，试找出一条路径，使得取得的数之和为最大。
输入格式
第一行为两个整数N，M，表示N×N的方格图，M个格子中放有数字。
接下来的每行有三个整数，第一个为行号数x，第二个为列号数y，第三个为在该行、该列上所放的数z。
接下来的每行有三个整数，第一个为行号数x，第二个为列号数y，第三个为在该行、该列上所放的数z。
输出格式
一个整数，表示一条路径上取得的最大的和。
输入输出样例
输入 #1
5 5 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5
输出 #1
15