题不会写，时间很紧，求奆佬

Question

4向方格取数
时间限制：1s
内存限制：128M
题目描述
【题目描述】
小猴进入了一个由n×m个格子组成的地区，每个格子都可以走。 第i行第j列的格子写着一个数v i,j
​ 小猴从地图的左上角（第1行第1列）出发，每次只能向：正下、正右、右上、右下这四个方向走一步。
问小猴到达右下角（第n行第m列）时，他经过的格子中的数总和最大是多少？
【输入格式】
第一行两个整数
n,m(1≤n,m≤1000)
接下来n行，每行m个整数，表示每个格子里的数。
【输出格式】
一个整数，小猴他经过的格子中的数的最大总和
【输入样例#1】
输入#1
4 4
1 1 9 10
2 5 -99 11
5 -10 99 2
-50 4 6 8
【输出样例#1】
输出#1
133
【样例解释】

说明/提示

1≤n,m≤1000

−1000≤v i,j≤1000
【编译语言】
C++14

Answer 1

代码如下：

我手敲的，而且使用了动态规划。

#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int walk(int i, int j, int n, int m, int array[][1000])
{
  // 如果超出数组边界，则返回一个非常小的非法值
  if ((i == n) || (i < 0)) {
    return -1001;
  }
  if ((j == m) || (j < 0)) {
    return -1001;
  }
  int current_num = array[i][j];
  // 如果到达了右下角，则返回该值，代表到达了终点，终止递归
  if ((i == n - 1) && (j == m - 1)) {
    return current_num;
  }
 
  int down = walk(i + 1, j, n, m, array) + current_num;
  int right = walk(i, j + 1, n, m, array) + current_num;
  int right_up = walk(i - 1, j + 1, n, m, array) + current_num;
  int right_down = walk(i + 1, j + 1, n, m, array) + current_num;

  // 如果比较上述的四个方向，取最大值返回
  int max = std::max(down, right);
  max = std::max(max, right_up);
  max = std::max(max, right_down);
  return max;
}
 
int main()
{
  int n;
  int m;
  cin >> n;
  cin >> m;
  int array[1000][1000] = {0};
 
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%d", &array[i][j]);
    }
  }
  int max = walk(0, 0, n, m, array);
  printf("%d\n", max);
  return 0;
}

输出结果：

4 4
1 1 9 10
2 5 -99 11
5 -10 99 2
-50 4 6 8
133