5897 - 矩阵移动(2)
题目描述
给定一个大小为 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] 的范围内）
输出
输出一个整数，表示从进入矩阵到离开矩阵，所有的路线中，经过数字和的最大值。
样例
输入
2 2 1 2 4 7
输出
8
输入
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
输出
427
输入
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
输出
660
标签
