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

解题思路:

用dp吧，记忆化搜索会有一点点爆栈

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <stdio.h>

#define MAX_N 51
#define MAX_M 51

using namespace std;

int Map[MAX_N][MAX_M];
int n, m;
int rowDir[] = { 1,0 };
int colDir[] = { 0,1 };
int dp[MAX_N][MAX_M][MAX_N][MAX_M];

int solve_dp()
{
	for (int i = m; i >= 1; i--)
	{
		for (int j = n; j >= 1; j--)
		{
			for (int k = m; k >= 1; k--)
			{
				for (int l = n; l >= 1; l--)
				{
					int newRow1, newRow2, newCol1, newCol2;
					int ans = 0;
					for (int a = 0; a < 2; a++)
					{
						newRow1 = i + rowDir[a];
						newCol1 = j + colDir[a];
						for (int b = 0; b < 2; b++)
						{
							newRow2 = k + rowDir[b];
							newCol2 = l + colDir[b];
							if (newRow1 >= 1 && newRow1 <= m && newCol1 >= 1 && newCol1 <= n && newRow2 >= 1 && newRow2 <= m && newCol2 >= 1 && newCol2 <= n
								&& newRow1 != newRow2 && newCol1 != newCol2)
							{
								ans = max(dp[newRow1][newCol1][newRow2][newCol2] + Map[newRow1][newCol1] + Map[newRow2][newCol2], ans);
							}
						}
					}

					dp[i][j][k][l] = ans;

				}
			}

		}
	}

	return dp[1][1][1][1];

}

int main()
{
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> Map[i][j];
	cout << solve_dp() << endl;
	return 0;
}