萌新求助,BFS会TLE一个点
查看原帖
萌新求助,BFS会TLE一个点
386876
BurningEnderDragon楼主2021/2/2 08:02

已经剪了一下枝防止一个格子被重复入队,但还是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

2021/2/2 08:02
加载中...