迷惑MLE
  • 板块P3395 路障
  • 楼主萧笙
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/11/29 13:54
  • 上次更新2023/11/5 07:06:10
查看原帖
迷惑MLE
299996
萧笙楼主2020/11/29 13:54
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define in inline 
#define re register
using namespace std;
struct node{
	int x,y,step;
};
const int dx[4]={0,0,-1,1};
const int dy[4]={1,-1,0,0};
int t,n;bool flag=false;
int sx[2003],sy[2003];
bool map[1003][1003],vis[1003][1003];

in void bfs(int x,int y,int step)
{
	queue<node>q;
	node now,next;
	now.x=x;now.y=y;now.step=step;
	q.push(now);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		int xx=now.x,yy=now.y,tt=now.step;
		if(xx==n&&yy==n)	{flag=true;break;}
		map[sx[now.step-1]][sx[now.step-1]]=true;
		for(re int i=0;i<=3;i++)
		{
			int nx=xx+dx[i],ny=yy+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!map[nx][ny]&&!vis[nx][ny])
				next.x=nx,next.y=ny,next.step=tt+1;
			vis[nx][ny]=true;
			q.push(next);	
		}	
	}
	return;
}

in int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>=48&&c<=57)	{x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

int main()
{
	t=read();
	while(t--)
	{
		memset(map,false,sizeof(map));
		memset(vis,false,sizeof(map));
		n=read();
		for(re int i=1;i<=2*n-2;i++)
			sx[i]=read(),sy[i]=read();
		vis[1][1]=true;
		bfs(1,1,0);
		if(flag)	printf("Yes\n");
		else	printf("No\n");	
	}
	return 0;
}

MLE评测记录

2020/11/29 13:54
加载中...