求助，记忆化搜索莫名其妙WA俩点

lmy80802345 @ 2021-08-19 22:00:41

#include <bits/stdc++.h>
using namespace std;
int a[1011][1011];
int  f[1005][1005];
int ser(int i,int j)
{
    if(f[i][j]>0)return f[i][j];
    int ans=1; 
//  printf("%d ", a[i][j]);
    if(a[i+1][j]<a[i][j]&&a[i+1][j]!=0)
    ans=max(ans,ser(i+1,j)+1);
    if(a[i][j+1]<a[i][j]&&a[i][j+1]!=0)
    ans=max(ans,ser(i,j+1)+1);
    if(a[i-1][j]<a[i][j]&&a[i-1][j]!=0)
    ans=max(ans,ser(i-1,j)+1);
    if(a[i][j-1]<a[i][j]&&a[i][j-1]!=0)
    ans=max(ans,ser(i,j-1)+1);
    f[i][j]=ans;
    return ans;
}
int main()
{
    int n,b; 
    scanf("%d %d",&n,&b);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=b;j++)
        {
            scanf("%d",&a[i][j]+1);
         } 
     } 
     int ans=0;
     for(int i=1;i<=n;i++)
     {
        for(int j=1;j<=b;j++)
        {
            int p=ser(i,j);
            f[i][j]=p;
            ans=max(ans,f[i][j]); 
         }
     }
     printf("%d",ans);
}

by songxiao @ 2021-08-19 22:06:50

@lmy80802345 不知为啥，我的代码和你的几乎一样

#include<bits/stdc++.h>
using namespace std;
int r,c,a[105][105],f[105][105]={0},ans=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int search(int x,int y)
{
    if(f[x][y]>0)
        return f[x][y];
    int t=1;
    int nx,ny;
    for(int i=0;i<4;i++)
    {
        nx=dx[i]+x;
        ny=dy[i]+y;
        if(nx>=0&&nx<r&&ny>=0&&ny<c&&a[x][y]<a[nx][ny])
        {
            int u=search(nx,ny)+1;
            if(u>t)
                t=u;
        }
    }
    f[x][y]=t;
    return t;
}
int main()
{
    cin>>r>>c;
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            cin>>a[i][j];
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            int t=search(i,j);
            f[i][j]=t;
            if(t>ans)
                ans=t;
        }
    }
    cout<<ans;
    return 0;
}

by lmy80802345 @ 2021-08-19 22:38:19

@Gorilla 找到问题了，以前的代码拿来改成记忆化，然后以前脑瘫scanf("%d",a[i][j]+1);多了个+1

by songxiao @ 2021-08-19 22:41:24

我谔谔，我复制成自己的代码了，怪不得那么像