记忆化搜索80分求助！

风起，即行 @ 2021-07-24 14:41:44

#include <bits/stdc++.h>
using namespace std;
int r,c,m[105][105],ans[105][105],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int dfs(int x,int y)
{
    if(ans[x][y]!=0) return ans[x][y];
    if((m[x+1][y]<m[x][y])&&(m[x][y+1]<m[x][y])&&(m[x-1][y]<m[x][y])&&(m[x][y-1]<m[x][y]))//搜索时从低往高搜
    //利用初值为零数组可以不设边界 
    {
        return 1;
        //最高点初始长度为一 
    }
    int maxh=0;
    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i],y1=y+dy[i];
        if((x1>0)&&(x1<=r)&&(y1>0)&&(y1<=c)&&(m[x1][y1]>m[x][y]))
        {
            maxh=max(dfs(x1,y1)+1,maxh);//搜索完某一点四个方向最值之后再确定该点的值 
        }
    }
    ans[x][y]=maxh;//把最值存入
    return maxh;
}
int main(){
    scanf("%d%d",&r,&c);
    int minh=99999999,p,q,maxh=1;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&m[i][j]);
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            dfs(i,j);
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(ans[i][j]>maxh)
            {
                maxh=ans[i][j];
            }
        }
    }
    printf("%d",maxh);
    return 0;
}

by Fan_Tuan @ 2021-07-24 15:17:48

#include <bits/stdc++.h>
using namespace std;
int r,c,m[105][105],ans[105][105],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int dfs(int x,int y)
{
    if(ans[x][y]!=0) return ans[x][y];
    // if((m[x+1][y]<m[x][y])&&(m[x][y+1]<m[x][y])&&(m[x-1][y]<m[x][y])&&(m[x][y-1]<m[x][y]))//搜索时从低往高搜
    // {
    //    return 1;
    // }
    int maxh=1;
    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i],y1=y+dy[i];
        if((x1>0)&&(x1<=r)&&(y1>0)&&(y1<=c)&&(m[x1][y1]>m[x][y]))
        {
            maxh=max(dfs(x1,y1)+1,maxh);//搜索完某一点四个方向最值之后再确定该点的值 
        }
    }
    ans[x][y]=maxh;//把最值存入
    return maxh;
}
int main(){
    scanf("%d%d",&r,&c);
    int minh=99999999,p,q,maxh=1;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&m[i][j]);
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            dfs(i,j);
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(ans[i][j]>maxh)
            {
                maxh=ans[i][j];
            }
        }
    }
    printf("%d",maxh);
    return 0;
}

by Fan_Tuan @ 2021-07-24 15:19:40

不一定是四周低中间高的位置才是1，只要是起点就是1，所以maxh要从1开始@风起，即行

by 风起，即行 @ 2021-07-24 15:36:53

@Fan_Tuan 谢谢大佬！这样思路就更顺了！

by L2396934825 @ 2021-09-25 10:17:42

@Fan_Tuan 谢谢dalao，点通我了。