为什么非要用方格取数的办法? 完全可以把两个问题独立思考

与方格取数不同的是, 一个方格只能经过一次
处理方案: 当走到同一个方格时,令$f[k][i1][i2] = -INF$, 则后继状态不会使用这个状态, 就保证了不会走过同一个方格

// AcWing 275. 传纸条, NOIP2008提高组
// 与方格取数不同的是, 一个方格只能经过一次
// 处理方案: 当走到同一个方格时,令f[k][i1][i2] = -INF, 则后继状态不会使用这个状态, 就保证了不会走过同一个方格

#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;

const int maxn = 55, INF = 1e9;
int m, n, a[maxn][maxn], f[2 * maxn][maxn][maxn];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];

    for (int k = 2; k <= m + n; k++)
    {
        for (int i1 = 1; i1 <= m; i1++)
        {
            for (int i2 = 1; i2 <= m; i2++)
            {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    if (i1 == i2 && k != 1 && k != m + n) { f[k][i1][i2] = -INF; continue; }    // 起点和终点必须都走
                    int t = a[i1][j1] + a[i2][j2];
                    int& v = f[k][i1][i2];
                    v = max(v, f[k - 1][i1 - 1][i2] + t);
                    v = max(v, f[k - 1][i1 - 1][i2 - 1] + t);
                    v = max(v, f[k - 1][i1][i2] + t);
                    v = max(v, f[k - 1][i1][i2 - 1] + t);
                }
            }
        }
    }
    cout << f[m + n][m][m] << endl;
    return 0;
}