第一个点过不去
  • 板块P3395 路障
  • 楼主honmamisuzu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/24 13:09
  • 上次更新2024/6/24 14:22:49
查看原帖
第一个点过不去
849218
honmamisuzu楼主2024/6/24 13:09
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int N = 1005;
int d[N][N],st[N][N];
int n;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void bfs(){
    queue<pii> q;
    d[1][1]=0;
    st[1][1]=1;
    q.push({1,1});
    while(q.size()){
        auto u=q.front();q.pop();
        int x=u.first,y=u.second;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<1||a>n||b<1||b>n) continue;
            if(st[a][b]) continue;
            if(d[x][y]+1>d[a][b]) continue;
            d[a][b]=d[x][y]+1;
            st[a][b]=1;
            q.push({a,b});
            if(a==n&&b==n) return;
        }
    }
}   
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;cin >> t;
    while(t--){
        memset(d,0x3f,sizeof d);
        memset(st,0,sizeof st);
        cin >> n;
        for(int i=1;i<=2*n-2;i++){
            int x,y;cin >> x >> y;
            d[x][y]=i;
        }
        bfs();
        if(d[n][n]==0x3f3f3f3f) cout << "No\n";
        else cout << "Yes\n";
    }
    return 0;
}
2024/6/24 13:09
加载中...