题解 P3395 【路障】

发现题解里没有人贴STL队列的代码0.0就是一个简单的bfs，注意路障的处理，注意数组别开小了和判断入队的合法性。 ```cpp #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; } ```