#4#5 wa 求助
  • 板块P3395 路障
  • 楼主qqq123456qqq
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/20 17:14
  • 上次更新2024/8/20 19:41:19
查看原帖
#4#5 wa 求助
1108007
qqq123456qqq楼主2024/8/20 17:14
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct qqt{
	int x,y;
}fi,la;
int n,a,lx[1005],zy[1005],p=1,o;
int f[1005][1005];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		o=0;
		p=1;
		memset(f,-1,sizeof(f));
		queue<qqt> q;
		fi.x=1;
		fi.y=1;
		f[1][1]=1;
		q.push(fi); 
		for(int j=1;j<=2*a-2;j++) scanf("%d%d",&lx[j],&zy[j]);
		if(a==1){
			printf("Yes\n");
			o=1;
			continue;
		}
		while(!q.empty()){
			//printf("%d ",q.size());
			fi=q.front();
			q.pop();
			for(int k=0;k<4;k++){
				int xx=fi.x+dx[k],yy=fi.y+dy[k];	
				if(xx>0&&xx<=a&&yy>0&&yy<=a&&f[xx][yy]==-1){
					if(xx==a&&yy==a){
						printf("Yes\n");
						o=1;
						break;
					}
					f[xx][yy]=f[fi.x][fi.y]+1;
					la.x=xx;
					la.y=yy;
					q.push(la);	
					if(f[xx][yy]>p){
						f[lx[p]][zy[p]]=0;
						p++;
					}
				}
			}
			if(o==1) break;
		}
		if(o==0) printf("No\n");
		o=0;
		p=1;
	}
	return 0;
}
2024/8/20 17:14
加载中...