WA4+T1,只是求调出80pts感谢
查看原帖
WA4+T1,只是求调出80pts感谢
929151
xxr___楼主2023/10/18 20:37

大佬们求调啊

#include<iostream>
using namespace std;
int a[10][10];
int b[10][10];
int f[10][10];
int f2[10][10];
int ans=0;
bool vis[10][10];
bool vs[10][10];
int n;
int dfs2(int x,int y,int sum){
	if(x==n&&y==n){
		return sum;
	}
	if(x<n&&vs[x+1][y]==0){
		vs[x+1][y]=1;
		dfs2(x+1,y,sum+a[x+1][y]);
		vs[x+1][y]=0;
	}
	if(y<n&&vs[x][y+1]==0){
		vs[x][y+1]=1;
		dfs2(x,y+1,sum+a[x][y+1]);
		vs[x][y+1]=0;
	}
}
void dfs1(int x,int y,int sum){
	if(x==n&&y==n){
		sum+=dfs2(1,1,a[1][1]);
		if(sum>ans)ans=sum;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				a[i][j]=b[i][j];
			}
		}
		return;
	}
	if(x<n&&vis[x+1][y]==0){
		vis[x+1][y]=1;
		dfs1(x+1,y,sum+a[x+1][y]);
		vis[x+1][y]=0;
	}
	if(y<n&&vis[x][y+1]==0){
		vis[x][y+1]=1;
		dfs1(x,y+1,sum+a[x][y+1]);
		vis[x][y+1]=0;
	}
}
signed main(){
	cin>>n;
	while(1){
		int x,y,w;
		cin>>x>>y>>w;
		if(x==0&&y==0&&w==0)break;
		a[x][y]=w;
		b[x][y]=a[x][y];
	}
	dfs1(1,1,a[1][1]);
	cout<<ans;
	return 0;
}
2023/10/18 20:37
加载中...