有些不解,dfs+记忆化
查看原帖
有些不解,dfs+记忆化
640477
biophitma_wby楼主2024/11/22 18:35

这里是用从[1,1]->[m,n]的两条路径AC了,而当一条从[1,1]->[m,n],另一条从[m,n]->[1,1]就会出错,求解释,谢谢dalao

#include<bits/stdc++.h>
using namespace std;
int m,n,cls[55][55];
int dp[55][55][55][55];
bool vis[55][55];
int dx[2]={0,1},dy[2]={1,0};
int dfs(int x1,int y1,int x2,int y2){
	if(x1==m&&y1==n&&x2==m&&y2==n){
		return 0;
	}else if(dp[x1][y1][x2][y2]!=-1){
		return dp[x1][y1][x2][y2];
	}else{
		int maxx=0;
		for(int i=0;i<2;i++){
			int xx1=x1+dx[i],yy1=y1+dy[i];
			if(xx1>=1&&xx1<=m&&yy1>=1&&yy1<=n&&vis[xx1][yy1]==0){
				vis[xx1][yy1]=1;
				for(int j=0;j<2;j++){
					int xx2=x2+dx[j],yy2=y2+dy[j];
					if(xx2>=1&&xx2<=m&&yy2>=1&&yy2<=n&&vis[xx2][yy2]==0){
						vis[xx2][yy2]=1;
						int res=cls[xx1][yy1]+cls[xx2][yy2];
						maxx=max(maxx,dfs(xx1,yy1,xx2,yy2)+res);
						vis[xx2][yy2]=0;
					}
				}
				vis[xx1][yy1]=0;
			}
		}
		dp[x1][y1][x2][y2]=maxx;
		return maxx;
	}
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&cls[i][j]);
		}
	}
	printf("%d",dfs(1,1,1,1));
	return 0;
} 
2024/11/22 18:35
加载中...