核心：动态规划

状态定义：f[i][j][k][l]表示第一个人走到i，j和第二个人走到k，l的所有走法的最大和
属性：max
状态计算：利用从下走或者从右走划分集合
f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]))+g[i][j]+g[k][l]
值得注意的是，每个方格只能走一次，因此当两个人都到同一个方格，该方格只需要加一次

#include<iostream>
using namespace std;
//状态定义：
int f[15][15][15][15];
int g[15][15];
int n;
int main(){
    cin>>n;
    while(1){
        int a, b, c;
        cin>>a>>b>>c;
        if(a==0 && b==0 && c==0)    break;
        g[a][b]=c;
        // cout<<g[a][b];
    }
    // f[1][1]=g[1][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                for(int l=1;l<=n;l++)
            {  
                f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k][l-1],f[i][j-1][k-1][l]))+g[i][j]+g[k][l];
                if(i==k&&j==l)  f[i][j][k][l]-=g[i][j];
            }
    cout<<f[n][n][n][n];
    return 0;
}