A71958 | $矩阵移动(2)$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定一个大小为 N \times M 的矩阵，你可以从矩阵的第 1 行的任意位置出发，按如下规则在矩阵中移动： 从任意的位置 i,j ，只能向其左下方 i+1,j-1 或者右下方 i+1,j+1 移动。 在从最后一行的任意位置离开矩阵前，不能走出矩阵。 矩阵中的每个格子上有一个整数，只要走到某格子，就需取走格子上的数字。 请求出，按上述规则，从进入矩阵到离开矩阵，所有的路线中，经过的格子的数字和最大是多少？

输入格式

输入两个整数 N,M，代表矩阵大小。（2 \le N \le 100，2 \le M \le 100） 接下来 N 行，每行有 M 个整数，表示矩阵中第 i 行的第 j 个格子的数字。（每个整数的值均在 [1, 10^5] 的范围内）

输出格式

输出一个整数，表示从进入矩阵到离开矩阵，所有的路线中，经过数字和的最大值。

输入输出样例

输入 #1

2 2
1 2
4 7

输出 #1

输入 #2

5 8
66 80 31 61 4 77 51 33
18 97 52 77 68 54 3 86
50 100 85 85 69 15 10 38
69 48 94 82 33 59 2 66
62 63 14 63 97 76 65 16

输出 #2

输入 #3

8 12
79 59 96 13 46 83 100 13 33 30 48 86
28 78 19 8 25 30 11 79 80 12 21 50
61 75 47 88 92 52 20 43 99 36 10 91
94 40 98 92 12 18 54 26 16 87 62 78
61 41 28 89 87 13 76 66 37 47 28 55
1 66 80 93 75 12 47 13 98 88 41 58
96 46 29 64 48 20 35 81 21 100 74 25
96 93 20 79 38 9 90 35 42 94 83 96

输出 #3

C++ 编辑器

输入

输出

A71958 | 矩阵移动(2)

题目描述

输入格式

输出格式

输入输出样例

A71958 | $矩阵移动(2)$