16分求调

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
};
int n,maxn=-1,ans=0;
int m[9][9];
vector<node> l;
vector<node> last;
void dfs(int x,int y,vector<node> &l,int cnt)
{
	node u;
	u.x=x,u.y=y;
	l.push_back(u);
	if(x>n || y>n) return;
	if(x==n && y==n){
		if(cnt>maxn){
			maxn=cnt;
			last.clear();
			last.resize(l.size());
			copy(l.begin(),l.end(),last.begin());
		}
	}
	dfs(x+1,y,l,cnt+m[x][y]);dfs(x,y+1,l,cnt+m[x][y]);
	l.pop_back();
	return;
}
int main()
{
	cin>>n;
	while(1)
	{
		int x,y,a;
		cin>>x>>y>>a;
		if(x==0 && y==0 && a==0) break;
		m[x][y]=a;
	}
	dfs(1,1,l,0);
	ans+=maxn;
	maxn=0;
	for(int i=0;i<last.size();i++)
	{
		m[last[i].x][last[i].y]=0;
	}
	dfs(1,1,l,0);
	cout<<ans+maxn;
	return 0;
}