求助bfs一次但 tle 4 8
查看原帖
求助bfs一次但 tle 4 8
169861
模拟王子楼主2023/12/18 15:57

求助bfs一次但tle4 8

本蒟蒻找不出哪里导致出现重复循环,求各位大佬帮助 手打队列 求助!!!!!!!

#include<stdio.h>
#include<string.h>
#include<math.h>
typedef struct Squeue{
	int front,rear;
	int x1[160001],y1[160001];
	int count;
}Squeue;
bool vis[401][401];int n,m;
int d[8][2]={{1,2},{-1,2},{-1,-2},{1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int sum[401][401];
void init(Squeue &S)
{
	S.front=0;
	S.rear=-1;
	S.count=0;
}
void push(Squeue &S,int x,int y)
{
	S.count++;
	S.x1[++S.rear]=x;
	S.y1[S.rear]=y;
	return ;
} 
int getx(Squeue &S) { return S.x1[S.front];}
int gety(Squeue &S) {return S.y1[S.front];}
void pop(Squeue &S){ S.front++;S.count--; return;}
bool empty(Squeue S)
{
	if(S.count<=0) return true;
	else return false;
}
void bfs(Squeue &s,int x0,int y0)
{
	push(s,x0,y0);
	while(!empty(s))
	{
		int x=getx(s),y=gety(s);
		pop(s);
		if(x<0 || x>n || y<0 || y>m) continue;
		if(vis[x][y]) continue;
		vis[x][y]=1;
		for(int i=0;i<=7;i++)
		{
			int x1=x+d[i][0],y1=y+d[i][1];
			if(x1<n && x1>=0 && y1<m && y1>=0)
			{		
				if(vis[x1][y1]) continue;
				sum[x1][y1]=sum[x][y]+1;
				push(s,x1,y1);
			}
		}
	}
	return ;
}
int main()
{
	Squeue s;
	init(s);
	scanf("%d%d",&n,&m);
	int x0,y0;
	scanf("%d%d",&x0,&y0);
	bfs(s,x0-1,y0-1);
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		if(sum[i][j]==0)
		{
			if(i==x0-1 && j==y0-1) printf("0 ");
			else printf("-1 ");
		}
		else printf("%d ",sum[i][j]);
		if(j==m-1) printf("\n");
	}
	return 0;
}
2023/12/18 15:57
加载中...