爆零求调!
  • 板块P3395 路障
  • 楼主Prince091214
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/8/29 20:41
  • 上次更新2025/8/30 12:29:18
查看原帖
爆零求调!
1838999
Prince091214楼主2025/8/29 20:41
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int T,n;
int x[2005],y[2005];
bool vis[1005][1005],mapp[1005][1005];
struct node{int x,y,time;};
node noww,nextt;
queue<node> q;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
bool bfs(node start){
    while(!q.empty()) q.pop();
    q.push(start);
    vis[start.x][start.y]=true;
    while(!q.empty()){
        noww=q.front();
        if(noww.x==n&&noww.y==n) return true;
        mapp[x[noww.time-1]][y[noww.time-1]]=true;
        q.pop();
        for(int i=0;i<4;i++){
            nextt.x=noww.x+dx[i];
            nextt.y=noww.y+dy[i];
            if(nextt.x<=n&&nextt.y<=n&&
               nextt.x>=1&&nextt.y>=1&&
               !vis[nextt.x][nextt.y]&&
              !mapp[nextt.x][nextt.y])
                q.push({nextt.x,nextt.y,noww.time+1});
        }
    }
    return false;
}
int main(){
    cin>>T;
    while(T--){
        memset(vis,false,sizeof(vis));
        cin>>n;
        for(int i=1;i<=2*n-2;i++) cin>>x[i]>>y[i];
        bfs({1,1,0}) ? cout<<"Yes\n" : cout<<"No\n";
    }
    return 0;
}
2025/8/29 20:41
加载中...