样例过了0分求助
  • 板块P3395 路障
  • 楼主x1489631649
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/15 11:28
  • 上次更新2024/6/15 14:40:07
查看原帖
样例过了0分求助
780505
x1489631649楼主2024/6/15 11:28
#include<bits/stdc++.h>
using namespace std;
int n,x,y,nx,ny;
int dx[10]={0,1,-1,0,0};
int dy[10]={0,0,0,1,-1};
int vis[1001][1001];
struct node{
	int x,y;
}q[10000005],a[1005];
int bfs()
{
	int h=1,t=1;
	q[h].x=1;
	q[h].y=1;
	vis[1][1]=1;
	while(h<=t)
	{
		if(q[h].x==n&&q[h].y==n)
		{
			cout<<"Yes"<<endl<<endl;
			return 0;
		}
		for(int i=1;i<=4;i++)
		{
			nx=q[h].x+dx[i];
			ny=q[h].y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&vis[nx][ny]==0)
			{
				q[++t].x=nx;
				q[t].y=ny;
				vis[nx][ny]=1;
			}
		}
		vis[a[t].x][a[t].y]=1;
		h++;
	}
	cout<<"No"<<endl<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(q,0,sizeof(q));
		memset(vis,0,sizeof(vis));
		memset(a,0,sizeof(a));
		cin>>n;
		for(int i=1;i<=2*n-2;i++)
			cin>>a[i].x>>a[i].y;
		bfs();
	}
	return 0;
}
2024/6/15 11:28
加载中...