蓝桥杯算法训练VIP-方格取数 （C++代码）

参考代码:

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

const int SIZE = 10;
int Map[SIZE][SIZE];
int Dp[SIZE][SIZE][SIZE][SIZE];
int Maps;

int DFS(int X1, int Y1, int X2, int Y2) {
	if (X1 > Maps || Y1 > Maps || X2 > Maps || Y2 > Maps)
		return 0;
	if (Dp[X1][Y1][X2][Y2] != -1)
		return Dp[X1][Y1][X2][Y2];
	int res = Map[X1][Y1] + Map[X2][Y2];
	if (X1 == X2 && Y1 == Y2)
		res -= Map[X2][Y2];
	res += max(max(DFS(X1, Y1 + 1, X2 + 1, Y2), DFS(X1, Y1 + 1, X2, Y2 + 1)), max(DFS(X1 + 1, Y1, X2 + 1, Y2), DFS(X1 + 1, Y1, X2, Y2 + 1)));
	return Dp[X1][Y1][X2][Y2] = res;
}

int main() {
	cin >> Maps; int posx, posy, w;
	while (cin >> posx >> posy >> w && posx && posy && w)
		Map[posx][posy] = w;
	memset(Dp, -1, sizeof Dp);
	cout << DFS(1, 1, 1, 1) << endl;
}