MLE了，为什么哩

muhouchen @ 2022-06-09 14:16:17

#include<stdio.h>
int n,x1,y1,x2,y2,count=10000000;
char arr[1002][1002];
const int direction1[5]={1,-1,0,0,0},direction2[5]= {0,0,1,-1,0};
void DFS(int a,int b,int temp);
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%s",arr[i]+1);
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    DFS(x1,y1,0);
    printf("%d",count);
    return 0;
}
void DFS(int a,int b,int temp)
{
   if(arr[a][b]=='1'||a<1||b<1||a>n||b>n) return;
   if(a==x2&&b==y2)
   {
    if(temp<count)
    count=temp;
    return;
   }
    for(int i=0;i<4;i++)
        DFS(a+direction1[i],b+direction2[i],temp+1); 
}

by SSqwq_ @ 2022-06-09 14:38:04

@penjiexiaodi 注意数据范围， n\leq 10^4 ，用深搜怎么想都会爆栈吧。

建议学习广搜相关内容。

by SSqwq_ @ 2022-06-09 14:38:40

啊说错了是 10^3 ，但裸的深搜肯定是过不去的。

by ningago @ 2022-06-09 14:40:30

@Summer_Sheep

洛谷好像不会爆栈（见此

但MLE这个东西还真挺玄学的

by SSqwq_ @ 2022-06-09 14:45:27

@ningago 谢谢，受教了

by SSqwq_ @ 2022-06-09 14:56:02

@penjiexiaodi 楼主您的 DFS 就算不 MLE 也会 TLE 的。

会重复走相同的路径，您需要让您的代码不走回头路。

by SSqwq_ @ 2022-06-09 14:57:08

我只针对这道题目来说，就算不走回头路， DFS 的效率比起 BFS 差得也不是一点半点。

by muhouchen @ 2022-06-09 15:04:13

@Summer_Sheep 这个我到DevC++上面运行的话会出现那个sigsegv异常，可以看出是哪里的毛病吗？

by muhouchen @ 2022-06-09 15:05:39

@Summer_Sheep 感谢感谢！！