RE求助
查看原帖
RE求助
372780
Controls_Wishes楼主2021/7/13 12:03

#2#3#4#5 RE.

#include<bits/stdc++.h>
using namespace std;
int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0},n,m[1005][1005],a[3005],b[3005];
bool win,f[1005][1005];
inline void bfs(){
	int se=0;
	queue<int>q1,q2;
	q1.push(1),q2.push(1);
		while(!q1.empty()&&!q2.empty()){
			for(int i=0;i<4;i++){
				int xx=q1.front()+dx[i],yy=q2.front()+dy[i];
				if(xx==n&&yy==n){
				    if(!f[xx][yy])win=1;
					return;
				}
				if(xx>=1&&yy>=1&&xx<=n&&yy<=n&&m[xx][yy]==-1&&!f[xx][yy]){
					q1.push(xx),q2.push(yy);
					m[xx][yy]=m[q1.front()][q2.front()]+1;
				}
			}
			f[a[++se]][b[se]]=1;
			if(f[n][n])return;
			q1.pop(),q2.pop();
		}
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=2*n-2;i++)
			scanf("%d%d",&a[i],&b[i]);
		memset(m,-1,sizeof(m)),memset(f,0,sizeof(f)),win=0,m[1][1]=0;
		if(n==1)printf("Yes\n");
		else{
			bfs();
			if(win)printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
}
2021/7/13 12:03
加载中...