题解 P3395 【路障】
Drug__Lover
2016-11-11 15:45:52
**先走再放路障**
**第一个点是在到达终点之前就已经被放上了路障，所以不能走了**
**纯纯的BFS**
\_我用了一个vis数组来记录路障和判断是否已经走过（反正都不能走。。。）\_
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,k,sum;
int x[1000001],y[1000001],vis[1001][1001];
int mx[5]={0,0,0,1,-1},my[5]={0,1,-1,0,0};
int fx[6000001],fy[1000001];
void bfs(int x1,int y1)
{
memset(vis,0,sizeof(vis));
k=0;
sum=0;
int h=0,t=1;
vis[1][1]=1;
fx[1]=x1;
fy[1]=y1;
while(h<t)
{
h++;
for(int i=1;i<=4;i++)
{
vis[x[sum]][y[sum]]=1;
if(x[sum]==n&&y[sum]==n) //如果在到达之前终点已经放上了路障，那就无法走到了，直接输出No就好了
{
k=0;
return;
}
int xx=fx[h]+mx[i],yy=fy[h]+my[i];
if(xx<=n&&xx>0&&yy<=n&&yy>0&&vis[xx][yy]==0)
{
t++;
vis[xx][yy]=1;
fx[t]=xx;
fy[t]=yy;
}
}
if(vis[n][n]==1) //如果终点已经走过并且不是路障那么就输出Yes
{
k=1;
return;
}
sum++;
}
}
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n;
for(int i=1;i<=2*n-2;i++)
{
cin>>x[i]>>y[i];
}
bfs(1,1);
if(k==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
```