蓝桥杯算法训练VIP-传纸条 （C++代码）

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int SIZE = 52;
int Map[SIZE][SIZE];
int Dp[SIZE][SIZE][SIZE][SIZE];
int Maph, Mapw;

int DFS(int posxst, int posyst, int posxnd, int posynd) {
    if (posxst > Maph || posyst > Mapw || posxnd > Maph || posynd > Mapw)
        return 0;
    if (Dp[posxst][posyst][posxnd][posynd] != -1)
        return Dp[posxst][posyst][posxnd][posynd];
    int res = Map[posxst][posyst] + Map[posxnd][posynd];
    if (posxst == posxnd && posyst == posynd)
        res -= Map[posxnd][posynd];
    res += max(max(DFS(posxst, posyst + 1, posxnd + 1, posynd), DFS(posxst, posyst + 1, posxnd, posynd + 1)), max(DFS(posxst + 1, posyst, posxnd + 1, posynd), DFS(posxst + 1, posyst, posxnd, posynd + 1)));
    return Dp[posxst][posyst][posxnd][posynd] = res;
}

int main() {
    scanf("%d%d", &Maph, &Mapw);
    for (int posx = 1; posx <= Maph; posx++)
        for (int posy = 1; posy <= Mapw; posy++)
            scanf("%d", &Map[posx][posy]);
    memset(Dp, -1, sizeof Dp);
    printf("%d\n", DFS(1, 1, 1, 1));
}