# 求助!P3395 路障 RE 出了什么问题呀

回复帖子

@XieMinghao 2021-04-08 09:08 回复
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=3000;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int a[N][N],b[N],c[N],st[N][N];
int n,t,k=1;

int bfs(PII start,PII end){
    if(start==end) return 1;     //如果起点就是终点 返回1 
    queue <PII> q;
    q.push(start);              //将起点压入队列中 
    st[start.x][start.y]=1;
    while(q.size()){
        PII t=q.front();         //取出队首 
        q.pop();              //弹出 
        for(int i=0;i<4;i++){                   
        int tx=t.x+dx[i];
        int ty=t.y+dy[i];                       //四个方向试探 
        if(tx<0||tx>n||ty<0||ty>n) continue;     //如果越界了 continue 
        if(st[tx][ty]!=-1) continue;          //如果已经走过了  continue 
        if(a[tx][ty]==1) continue;               //如果有障碍 continue 
        st[tx][ty]=1;                                //可以走,把可以走的都表记为1 
        if(make_pair(tx,ty)==end)
            return 1;                                //可以走到终点,返回1 
        q.push({tx,ty});               
      }
        a[b[k]][c[k]]=1;                             // 每过一秒,就把障碍添加到地图 a中 
        k++;                                          
        } 
    }

int main(){
        cin>>t;
        while(t>0){
        t--;
        memset(a,0,sizeof a);      //地图清零 
        memset(b,0,sizeof b);       
        memset(c,0,sizeof c);
        memset(st,-1,sizeof st);    //状态清零 
        scanf("%d",&n); 
        for(int i=1;i<=2*n-2;i++){
            scanf("%d %d",&b[i],&c[i]);
        }
        PII start,end;
        start={1,1};
        end={n,n};
        int res=bfs(start,end);
        if(res==1) cout<<"Yes";
        else  cout<<"No";
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。