萌新求助,BFS会TLE一个点

P1434 [SHOI2002] 滑雪

BurningEnderDragon @ 2021-02-02 08:02:31

已经剪了一下枝防止一个格子被重复入队,但还是TLE一个点……

评测记录

代码如下:

#include <cstdio>
#define XX Queue[Head].X
#define YY Queue[Head].Y
#define SS Queue[Head].Step
int R,C,Square[100][100],Max_Step[100][100]={},Head=0,Tail=0,Ans=1,Final_Ans=1;
struct Point
{
    int X,Y,Step;//X是纵坐标,Y是横坐标 
}Queue[20000];
void Push(int x,int y,int step)
{
    Queue[Tail].X=x;
    Queue[Tail].Y=y;
    Queue[Tail].Step=step;
    ++Tail;
    if(Tail==20000)
    {
        Tail=0;
    }
}
void Pop()
{
    ++Head;
    if(Head==20000)
    {
        Head=0;
    }
}
bool Empty()
{
    return Head==Tail?1:0;
}
void BFS(int x,int y)
{
    if(x>=0&&x<=R-1&&y>=0&&y<=C-1&&Square[x][y]<Square[XX][YY]&&SS+1>Max_Step[XX][YY])
    {
        Push(x,y,SS+1);
        if(Max_Step[x][y]<SS+1)
        {
            Max_Step[x][y]=SS+1;
        }
    }
    return ;
}
int main()
{
    scanf("%d%d",&R,&C);
    for(int i=0;i<=R-1;++i)
    {
        for(int j=0;j<=C-1;++j)
        {
            scanf("%d",&Square[i][j]);
        }
    }
    for(int i=0;i<=R-1;++i)
    {
        for(int j=0;j<=C-1;++j)
        {
            Ans=1;
            Push(i,j,1);
            while(!Empty())
            {
                if(SS<Max_Step[XX][YY])
                {
                    goto Next;
                }
                if(Queue[Head].Step>Ans)
                {
                    Ans=Queue[Head].Step;
                }
                BFS(XX-1,YY);
                BFS(XX+1,YY);
                BFS(XX,YY-1);
                BFS(XX,YY+1);
                Next:;
                Pop();
            }
            if(Ans>Final_Ans)
            {
                Final_Ans=Ans;
            }
        }
    }
    printf("%d\n",Final_Ans);
    return 0;
}

救救孩子吧QWQ


by ollo @ 2021-02-02 08:42:10

这题不是记搜吗......


by TYxxj @ 2021-02-02 09:47:41

打表(当我啥都没说)


|