全wa求助
  • 板块P3395 路障
  • 楼主安舒阳
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/11/15 12:05
  • 上次更新2023/11/5 08:01:09
查看原帖
全wa求助
321068
安舒阳楼主2020/11/15 12:05
#include<bits/stdc++.h>
using namespace std;
struct Node{
	int x,y;
}zhang[2005];
int dis[1005][1005];
int vis[1005][1005];
int dx[5]={0,1,-1,0};
int dy[5]={1,0,0,-1};
int n;
void bfs(){
	queue<Node> q;
	vis[1][1]=1;
	dis[1][1]=0;
	q.push((Node){1,1});
	while(!q.empty()){
		Node now=q.front();
		q.pop();
		int k=dis[now.x][now.y];
		if(now.x==n&&now.y==n){
			printf("Yes\n");
			return ;
		}
		vis[zhang[k+1].x][zhang[k+1].y]=1;
		for(int i=0;i<4;i++){
			int x=now.x+dx[i];
			int y=now.y+dy[i];
			if(x>0&&y>0&&x<=n&&y<=n&&vis[x][y]!=1){
				q.push((Node){x,y});
				vis[x][y]=1;
				dis[x][y]=k+1;
			}
		}
	}
	printf("No\n");
	return ;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(dis,0,sizeof(dis));
		memset(vis,0,sizeof(vis));
		scanf("%d",&n);
		int qqq=n*2-2;
		for(int i=1;i<=qqq;i++){
			scanf("%d %d",&zhang[i].x,&zhang[i].y);
		}
		bfs();
	}
	return 0;
}
2020/11/15 12:05
加载中...