70pts记忆化搜索求助
查看原帖
70pts记忆化搜索求助
664744
Nwayy楼主2022/11/29 18:54
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,ans;
int mp[205][205],f[205][205];
int dx[]={-1,-1,-1};
int dy[]={-1,0,1};
int dfs(int x,int y){
//    printf("%d %d\n",x,y);
    if(x<1 || x>n || y<1 || y>m) return 0;
    if(f[x][y]!=-1) return f[x][y];
    int p,q=-1e9;
    for(int i=0;i<=2;i++){
        int nx=x+dx[i],ny=y+dy[i];
        p=dfs(nx,ny)+mp[nx][ny];
        q=max(q,p);
    }
    return f[x][y]=q;
}
signed main(){
    for(i=1;i<=200;i++){
        for(j=1;j<=200;j++) f[i][j]=-1;
    }
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++) scanf("%d",&mp[i][j]);
    }
    ans=max(ans,dfs(n,m/2)+mp[n][m/2]);
    memset(f,-1,sizeof(f));
    ans=max(ans,dfs(n,m/2-1)+mp[n][m/2-1]);
    memset(f,-1,sizeof(f));
    ans=max(ans,dfs(n,m/2+1)+mp[n][m/2+1]);
    printf("%d",ans);
    return 0;
}  

WA了三个点,求调。

2022/11/29 18:54
加载中...