我的取巧代码能过（离起点最远的部分不跑，将图的无意义的部分删掉）

主要这题的数据里没有大小为 9 时有有价值的格子贴边的情况，连我 $O_{2^{n^2}}$ 的复杂度都能过 (应该是这个复杂度吧，没仔细算)

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10][10];
int ans=0;
bool vis[10][10];
int don,rit;
void solve(int x,int y,int sum){
    if(x==don&&y==rit){
        ans=max(ans,sum);
        return;
    }
    if(x<don)solve(x+1,y,sum+a[x+1][y]*(1-vis[x+1][y]));
    if(y<rit)solve(x,y+1,sum+a[x][y+1]*(1-vis[x][y+1]));
    
}
void dfs(int x,int y,int sum){
    if(x==don&&y==rit){
        /*
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout << vis[i][j] << ' ';
            }
            cout << endl;
        }
        cout << sum << endl;*/
        solve(1,1,sum);
        return;
    }
    if(x<don){
        vis[x+1][y]=1;
        dfs(x+1,y,sum+a[x+1][y]);
        vis[x+1][y]=0;
    }
    if(y<rit){
        vis[x][y+1]=1;
        dfs(x,y+1,sum+a[x][y+1]);
        vis[x][y+1]=0;
    }
}
int main(){
    cin >> n;
    int x,y,d;
    cin >> x >> y >> d;
    while(x!=0){
        a[x][y]=d;
        cin >> x >> y >> d;
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
    */
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--){
            if(a[i][j]>0){
                rit=max(rit,j);
                break;
            }
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--){
            if(a[j][i]>0){
                don=max(j,don);
                break;
            }
        }
    } 
    //cout << don << ' ' << rit <<endl;
    vis[1][1]=1;
    dfs(1,1,a[1][1]);
    cout << ans;
    return 0;
}