#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAX = 55; int grid[MAX][MAX]; // 存储每个同学的好感度 int dp[105][MAX][MAX]; // dp[k][i1][i2]：k步后，路径1在(i1,j1)，路径2在(i2,j2)的最大和 int m, n; // 计算最大值的辅助函数（四个方向的最大值） int max4(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); } int main() { cin >> m >> n; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { cin >> grid[i][j]; } } // 初始化DP数组为-1（表示未访问） memset(dp, -1, sizeof(dp)); dp[0][1][1] = 0; // 初始状态：0步，都在(1,1)，和为0 // 总步数：从(1,1)到(m,n)需要走(m+n-2)步 for (int k = 1; k <= m + n - 2; ++k) { // 枚举第一条路径的横坐标i1（范围：1~min(k+1, m)） for (int i1 = 1; i1 <= m; ++i1) { int j1 = k + 2 - i1; // 第一条路径的纵坐标 if (j1 < 1 || j1 > n) continue; // 超出矩阵范围，跳过 // 枚举第二条路径的横坐标i2（范围：1~min(k+1, m)） for (int i2 = 1; i2 <= m; ++i2) { int j2 = k + 2 - i2; // 第二条路径的纵坐标 if (j2 < 1 || j2 > n) continue; // 超出矩阵范围，跳过 // 上一步的四种可能：(下,下)、(下,右)、(右,下)、(右,右) int prev1 = dp[k-1][i1-1][i2-1]; // 路径1下，路径2下 int prev2 = dp[k-1][i1-1][i2]; // 路径1下，路径2右 int prev3 = dp[k-1][i1][i2-1]; // 路径1右，路径2下 int prev4 = dp[k-1][i1][i2]; // 路径1右，路径2右 int max_prev = max4(prev1, prev2, prev3, prev4); if (max_prev == -1) continue; // 上一步无合法路径，跳过 // 计算当前位置的好感度和 if (i1 == i2 && j1 == j2) { // 两条路径走到同一位置，只加一次 dp[k][i1][i2] = max_prev + grid[i1][j1]; } else { // 不同位置，加两次 dp[k][i1][i2] = max_prev + grid[i1][j1] + grid[i2][j2]; } } } } // 最终结果：走(m+n-2)步后，都到达(m,n) cout << dp[m+n-2][m][m] << endl; return 0; }