尝试暴力还错了...
查看原帖
尝试暴力还错了...
366595
zty_luogu楼主2021/8/22 16:11

求助

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define f(III,MMM,NNN) for(register int III=MMM;III<=NNN;III++)
typedef long long int ll;
const int inf=0x3f3f3f3f;
int n,m;
int a[1010][1010]={};
int vis[1010][1010]={};
const int dx[3]={1,-1,0},
		  dy[3]={0,0, 1};

int ans=-inf;
void search(int x,int y,int sum){
	if(x==m&&y==n){
		ans=max(sum,ans);
		return ;
	}
//	if(sum>=ans&&ans!=-inf){
//		return ;
//	}
	for(int i=0;i<3;i++){
		if(x+dx[i]>=1&&y+dy[i]>=1&&
		   x+dx[i]<=m&&y+dy[i]<=n&&
		   !vis[x+dx[i]][y+dy[i]]){
		   	vis[x+dx[i]][y+dy[i]]=1;
			search(x+dx[i],y+dy[i],sum+a[x+dx[i]][y+dy[i]]);
		   	vis[x+dx[i]][y+dy[i]]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	search(1,1,a[1][1]);
	cout<<ans;
	return 0;
}

2021/8/22 16:11
加载中...