bfs全wa,自己拿样例测试找不出问题,麻烦大佬看看问题在哪里
  • 板块P3395 路障
  • 楼主orange333
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/4/2 23:55
  • 上次更新2023/10/23 19:34:17
查看原帖
bfs全wa,自己拿样例测试找不出问题,麻烦大佬看看问题在哪里
979481
orange333楼主2023/4/2 23:55
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second

typedef pair<int ,int> PII;
const int N=1010;
int n,t;
int c[N][N];
int dist[N][N];
bool v[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool f;
queue <PII> q;

void bfs(int a,int b){
    
    dist[a][b]=0;
    v[a][b]=true;
    q.push({a,b});
    
    while(q.size()){
        auto t=q.front();
        q.pop();
        
        for(int i=0;i<4;i++){
            int x1=t.fi+dx[i],y1=t.se+dy[i];
           
            if(x1<1||x1>n||y1<1||y1>n)continue;
            if(v[x1][y1])continue;
            if(dist[x1][y1]>0)continue;
            if(dist[t.fi][t.se]+1>c[x1][y1]){
                //cout<<x1<<y1<<c[x1][y1]<<endl;
                continue;
            }
            if(x1==n&&y1==n){
                f=true;break;
            }

            v[x1][y1]=true;
            dist[x1][y1]=dist[t.fi][t.se]+1;
            q.push({x1,y1});
            
        }
    }
    
}

int main(){
    cin>>t;
    int x,y;
    while(t--){
         cin>>n;
         f=false;
         memset(c,0x3f,sizeof c);
         for(int i=1;i<=n;i++){
            cin>>x>>y;
            c[x][y]=i;
         }
         memset(dist,-1,sizeof dist);
         memset(v,false,sizeof v);
        bfs(1,1);
        if(f){
            //cout<<dist[n][n];
            cout<<"Yes"<<endl;
        }
        else{
            //cout<<dist[n][n];
            cout<<"No"<<endl;
        }
    }
    
}
2023/4/2 23:55
加载中...