题解 P3395 【路障】

luoyue123 · 2017-10-25 12:55:17 · 题解

发现题解里没有人贴STL队列的代码0.0就是一个简单的bfs，注意路障的处理，注意数组别开小了和判断入队的合法性。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
struct point{
    int x,y,time;//x,y是点的坐标，time是时间。
};
point a,z[MAXN];//z数组要开的足够大啊。（大于2*n-2）之前开小RE了好几次。。
queue<point>q; //STL队列
bool vis[MAXN][MAXN];
int ax[]={0,0,1,-1},ay[]={1,-1,0,0},n,g;//ax ay是四个方向判断
void bfs(){
    bool flag=0;
    while(!q.empty()){
        point u=q.front();
        q.pop();
        if(u.x==n&&u.y==n){
            printf("Yes\n");
            flag=1;
            break;
        }
        vis[z[u.time-1].x][z[u.time-1].y]=1;//因为是BFS，时间和入队顺序是按时间层层递进的。
        for(int i=0;i<=3;i++){
            if(!vis[u.x+ax[i]][u.y+ay[i]]&&u.x+ax[i]>=1&&u.x+ax[i]<=n&&u.y+ay[i]>=1&&u.y+ay[i]<=n){//判断合法性
                vis[u.x+ax[i]][u.y+ay[i]]=1;//直接标记为走过以免重复入队
                q.push((point){u.x+ax[i],u.y+ay[i],u.time+1});//入队
            }
        }
    }
    if(flag==0)printf("No\n");
}
int main(){
//    freopen("3395.in","r",stdin);
//    freopen("3395.out","w",stdout);
    scanf("%d",&g);
    for(int l=1;l<=g;l++){
        memset(vis,0,sizeof(vis));
        memset(z,0,sizeof(z));
        scanf("%d",&n);
        for(int i=1;i<=2*n-2;i++){
            scanf("%d%d",&z[i].x,&z[i].y);
        }
        while(!q.empty()){
            q.pop();//清空数组
        }
        q.push((point){1,1,1});
        vis[1][1]=1;//避免走回起点
        bfs();
    }
    return 0;
}