50pts,MLE,求调

P1434 [SHOI2002] 滑雪

afreshmanofclanguage @ 2024-08-30 16:44:27

#include<bits/stdc++.h>
using namespace std;
short r,c,arr[102][102],m,maxi,maxj,mem[102][102];
short xm[4] = {1,0,-1,0};
short ym[4] = {0,1,0,-1};
int dfs(int x,int y)
{
    if(mem[x][y] != -1) return mem[x][y];
    if(x < 1 || x > r || y < 1 || y > c) return 0;
    if(x == maxi && y == maxj) return mem[x][y] = 1; // 到最高点了
    int ans = 0;
    for(int i = 0;i < 4;i++)
    {
        int a = x + xm[i];int b = y + ym[i];
        if(arr[a][b] < arr[x][y]) continue;
        ans = max(ans,dfs(a,b));
    }
    return mem[x][y] = ans + 1;
}
int main()
{
    int ans = 0;
    memset(mem,-1,sizeof(mem));
    cin >> r >> c;
    for(int i = 1;i <= r;i++)
    {
        for(int j = 1;j <= c;j++)
        {
            scanf("%d",&arr[i][j]);
            if(arr[i][j] > m)
            {
                m = arr[i][j];
                maxi = i;
                maxj = j;
            }
        }
    }
    for(int i = 1;i <= r;i++)
        for(int j = 1;j <= c;j++)
            ans = max(ans,dfs(i,j));
    cout << ans;
    return 0;
}

by glass_goldfish @ 2024-08-30 16:48:26

你的visit[][]去哪了


by glass_goldfish @ 2024-08-30 16:48:49

@afreshmanofclanguage


by afreshmanofclanguage @ 2024-08-30 18:47:52

@glass_goldfish ....我好像不知道你说的vis数组是什么意思...我现在已经MLE了,再开一个数组又要爆内存了呀


by a11223344 @ 2024-09-10 21:47:54

第15行,高度相等的不能走,会出现自环(类似于 1 -> 2,2 -> 1, 1 -> 2,...,一直循环就会栈溢出)

if(arr[a][b] >= arr[x][y]) continue;

|