求助
  • 板块P3395 路障
  • 楼主_will_
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/12/21 19:57
  • 上次更新2023/10/28 13:56:42
查看原帖
求助
443059
_will_楼主2021/12/21 19:57
#include<bits/stdc++.h>
using namespace std;
inline void read(int &s){//快读(无符号int) 
    s=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^48);
}

int n;
int dt[1005][1005],b[1005][1005];
struct node{
	int x,y,t;
};
void bfs(){
	queue <node> q;
	node a;
	a.x=1; a.y=1; a.t=0;
	q.push(a);
	while(!q.empty()){
		a=q.front(); q.pop();
		int x=a.x, y=a.y, t=a.t;
		if(x==n && y==n){
			puts("Yes");
			return;
		}
		if(x+1<=n && (t+1<=dt[x+1][y] || dt[x+1][y]==-1) && b[x+1][y]==0){
			b[x+1][y]=1;
			a.x=x+1, a.y=y, a.t=t+1;
			q.push(a);
		}//down
		if(x-1>=1 && (t+1<=dt[x-1][y] || dt[x-1][y]==-1) && b[x-1][y]==0){
			b[x-1][y]=1;
			a.x=x-1, a.y=y, a.t=t+1;
			q.push(a);
		}//up
		if(y-1>=1 && (t+1<=dt[x][y-1] || dt[x][y-1]==-1) && b[x][y-1]==0){
			b[x][y-1]=1;
			a.x=x, a.y=y-1, a.t=t+1;
			q.push(a);
		}//left
		if(y+1<=n && (t+1<=dt[x][y+1] || dt[x][y+1]==-1) && b[x][y+1]==0){
			b[x][y+1]=1;
			a.x=x, a.y=y+1, a.t=t+1;
			q.push(a);
		}//right
	}
	puts("No");
}
int main(){
	int t;cin>>t;
	while(t--){
		memset(dt,-1,sizeof(dt));
		memset(b,0,sizeof(b));
		cin>>n;
		for(int i=1;i<=n;i++){
			int x,y;
			read(x);read(y);
			dt[x][y]=i;
		}
		bfs();
	}
	return 0;
}
2021/12/21 19:57
加载中...