2882 - 矩阵求和
题目描述
有一个 N \times M 的矩阵（M 一定是奇数），矩阵的第 i 行第 j 列有整数 A_{ij}。
在矩阵中任意的位置，只能沿着如下图所示的 5 个方向向上移动（不能出矩阵的边界）。
请编程计算出，从矩阵最后一行最中间位置的正下方开始，按照上述移动规则移动到矩阵的第 1 行，经过数字和的最大值是多少？
比如，有如下图所示的矩阵，从标记为 H 的位置（最后一行最中间位置的正下方）出发，沿红色箭头所示的方向，经过的数字和最大。
输入
第 1 行有 2 个整数 N 和 M。
接下来 N 行，每行有 M 个整数，用空格隔开。
输出
输出经过数字和的最大值。
样例
输入
6 7 16 4 3 12 6 0 3 4 -5 6 7 0 0 2 6 0 -1 -2 3 6 8 5 3 4 0 0 -2 7 -1 7 4 0 7 -5 6 0 -1 3 4 12 4 2
输出
51
说明
数据范围
对于 100\% 的数据，1 \le N,M \le 200，-10^5 \le A_{ij} \le 10^5，测试数据确保答案在 [-10^9,10^9] 的范围内。
来源
东方博宜OJ
标签