求助，5个点MLE

hang09 @ 2022-08-20 22:00:49

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int h[110][110];
int rec[110][110];
int ans = 0;

int f(int x,int y)
{
    if(rec[x][y] != -1)return rec[x][y];
    int an = 0;
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > m)continue;//越界
        if(h[nx][ny] > h[x][y])continue;
        an = max(f(nx,ny),an);//4个方向依次枚举，取最长
    }
    return rec[x][y] = an + 1;
}

int main()
{
    memset(rec, -1,sizeof(rec));
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&h[i][j]);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            ans = max(ans,f(i,j));
        }
    }
    printf("%d\n",ans);
    return 0;
}

by hang09 @ 2022-08-23 20:08:37

@159号程序员

by 159号程序员 @ 2022-08-23 20:22:13

@hang09

#include <bits/stdc++.h>
using namespace std;
int r, c, a[105][105], vis[105][105], ans;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int dfs(int posx, int posy)
{
    if(vis[posx][posy]) return vis[posx][posy];
    vis[posx][posy] = 1;
    for(int i = 0; i < 4; i++)
    {
        int x = dx[i] + posx, y = dy[i] + posy;
        if(x >= 0 && y >= 0 && x < r && y < c && a[posx][posy] > a[x][y])
        {
            dfs(x, y);
            vis[posx][posy] = max(vis[posx][posy], vis[x][y] + 1);
        }
    }
    return vis[posx][posy];
}
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++)
            ans = max(ans, dfs(i, j));
    cout << ans;
    return 0;
}