求助!第一个点Wa了,后面的都AC了
查看原帖
求助!第一个点Wa了,后面的都AC了
226367
glorious_dream楼主2021/12/21 20:50
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0' ; ch=getchar();}
	return x*f;
}
const int dx[] = {0,1,0,-1};
const int dy[] = {-1,0,1,0};
struct dat{
	int time,pos;
}a[1010][1010];
bool vis[1010][1010];
int flag;
int n;
void bfs(){
	queue<int>qx;
	queue<int>qy;
	queue<int>qs;
	qx.push(1);
	qy.push(1);
	qs.push(1);
	vis[1][1] = 1;
	while(!qx.empty()){
		int x = qx.front();
		int y = qy.front();
		int s = qs.front();
		qx.pop();qy.pop();qs.pop();
		if(x==n && y==n){
			printf("Yes\n");
			flag = 1;
			return;
		}
		for(register int i(0) ; i<4 ; i=-~i){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx>0&&yy>0&&xx<=n&&yy<=n&&!vis[xx][yy]&&(a[xx][yy].pos==0||(a[xx][yy].pos==1&&a[xx][yy].time>=s))){
				qx.push(xx);
				qy.push(yy);
				qs.push(s+1);
				vis[xx][yy] = 1;
			}
			if(xx==n && yy==n){
				printf("Yes\n");
				flag = 1;
				return;
			}
		}
	}
}
int main(){
	int t;
	t=read();
	while(t--){
		flag = 0;
		n=read();
		memset(a,0,sizeof(a));
		memset(vis,0,sizeof(vis));
		for(register int i(1) ; i<=2*n-2 ; i=-~i){
			int x,y;
			x=read();y=read();
			a[x][y].pos = 1;
			a[x][y].time = i;
		}
		bfs();
		if(flag == 0) printf("No\n");
	}
	return 0;
}
2021/12/21 20:50
加载中...