这里是用从[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;
}