求助,为什么MLE

P1434 [SHOI2002] 滑雪

abruce @ 2018-09-16 11:52:29

#include<bits/stdc++.h>
using namespace std;
int maps[101][101],s[101][101],dx[4]={-1,0,1,0},dy[4]={0,-1,0,1},n,m,maxx=0;
int bfs(int stx,int sty)
{
    if(s[stx][sty]!=-1)return s[stx][sty];
    int a=1;
    for(register int i=0;i<=3;i++)
    {
        if(maps[stx][sty]>maps[stx+dx[i]][sty+dy[i]])
        a=max(a,bfs(stx+dx[i],sty+dy[i]+1));
    }   
    return a;
}
int main()
{
    cin>>n>>m;
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            cin>>maps[i][j];
            s[i][j]=-1;
        }
    }
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            maxx=max(maxx,bfs(i,j));
        }
    }
    cout<<maxx;
    return 0;
}

by WA鸭鸭 @ 2018-09-16 11:54:29

不知道,洛谷IDE您样例都MLE


by abruce @ 2018-09-16 11:56:54

@WA鸭鸭 可一个测试点才648kb


by A星际穿越 @ 2018-09-16 11:58:18

RE会导致MLE、TLE等多种奇怪的结果所以可能是你的代码RE了


by abruce @ 2018-09-16 12:00:12

@A星际穿越 但我本地没问题


by abruce @ 2018-09-16 12:01:08

@A星际穿越 是RE了


by A星际穿越 @ 2018-09-16 12:01:23

@zym0522 说不定你交上去就数组越界啦、无限递归啦什么的,然后给你判成MLE了


by abruce @ 2018-09-16 12:04:03

@A星际穿越 不是,是 bfs错误


by Itst @ 2018-09-16 12:14:47

这不是dfs吗是bfs?

应该在return a之前加一个s[stx][sty]=a,要不然就没有记忆化的效果了


by A星际穿越 @ 2018-09-16 12:15:55

@zym0522 第一,你那是深搜dfs。第二,你没判边界,导致数组越界


by A星际穿越 @ 2018-09-16 12:17:12

第三,同楼上Itst大佬所讲,这可能会导致无限递归


|