记忆化搜索WA 15分求调
查看原帖
记忆化搜索WA 15分求调
322437
xxxalq楼主2023/8/13 09:43
#include<iostream>
using namespace std;
const int inf=-0x3f3f3f3f;
int n,m,a[1005][1005],dp[1005][1005],xy[3][2]={{1,0},{0,1},{-1,0}};
bool mk[1005][1005]; 
int dfs(int x,int y){
	if(dp[x][y]>inf){
		return dp[x][y];
	}
	if(x==n&&y==m){
		return dp[x][y]=a[x][y];
	}
	for(int i=0;i<3;i++){
		int xx=x+xy[i][0],yy=y+xy[i][1];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mk[xx][yy]==false){
			mk[xx][yy]=true;
			dp[x][y]=max(dp[x][y],dfs(xx,yy)+a[x][y]);
			mk[xx][yy]=false;	
		}
	}
	return dp[x][y];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			dp[i][j]=inf;
		}
	}
	mk[1][1]=true;
	printf("%d\n",dfs(1,1));
	return 0;
}
2023/8/13 09:43
加载中...