十五分求助
查看原帖
十五分求助
100091
GaryH楼主2020/11/21 16:48
#include<bits/stdc++.h>
#define maxn 1000
#define inf 10000000000000000
using namespace std;
int n,m;
int vis[maxn+10][maxn+10];
long long a[maxn+10][maxn+10];
long long dp[maxn+10][maxn+10];
int nxt[3][2]={{1,0},{0,1},{-1,0}};
inline void dfs(int x,int y,long long ans){
	if(ans<dp[x][y]){
		return;
	}
	dp[x][y]=ans;
	if(x==n&&y==m){
		return;
	}
	register int nx,ny;
	for(int i=0;i<3;i++){
		nx=x+nxt[i][0];
		ny=y+nxt[i][1];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&vis[nx][ny]==0){
			vis[nx][ny]=1;
			dfs(nx,ny,ans+a[nx][ny]);
			vis[nx][ny]=0;
			
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
			dp[i][j]=-inf;
		}
	}
	vis[1][1]=1;
	dfs(1,1,a[1][1]);
	printf("%lld",dp[n][m]);
	return 0;
}
2020/11/21 16:48
加载中...