引人自闭的 BFS 之一：路障（P3395）
喝烘箱
2019-01-12 16:08:51
# 这么简单的题居然是D1T1！！！！
## 我都惊到了！！！
咳咳，不皮了，先说一下思路。
#### 广搜从起点开始搜索太慢了！而且没有必要！~~虽然要过这道题的数据是轻轻松松~~
#### 我们可以直接广搜路障！！！
#### 然后时间复杂度就会直接缩小到天的另一边去！！！
首先！这是一个矩阵！
所以在无障碍的情况下这个熊孩子跑到每一个点的时间可以用数组下标直接算出来
因为我们到的每一个点的最短距离就是这两个点的横坐标之差与纵坐标之差的和
| _1_ | _2_ | _3_ | _4_ | _5_ | _6_ | _7_ | _8_ | _9_ |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | 起点 |-- | -- | -- | -- | -- | -- | -- |
| 3 | | | | | | | | |
| 4 | | | | | | | | |
| 5 | | | | | | | o | |
| 6 | | o | | | | | | |
| 7 | | | | | | | | |
| 8 | | | | | o | | | |
| 9 | | | | | | | | o |
很容易就能发现，以任意一个点为终点都可以与起点连成一个矩形
然后又因为只能向上下左右四个方向移动。。。
所以步数最短的走法就是一直想终点方向走，即只向下或向右走。。。
之后后就不用我说了吧
~~这其实是小学奥数~~
其次！如果在某一时刻落下路障时这个熊孩子已经走过了这个点，那这个路障就和没放完全没有区别，因为最短距离一定是一直向下或向右走，所以只要过了那个位置就再也不会走到那个位置了！
所以那个路障就可以当做没有出现过！
还有一件有意思的事，就是当所有的路障都落下来的时候，如果这些路障之间有空隙，那么他们就不能拦住这个熊孩子！
举个栗子，我们用X来代表路障，具体来看一下
| 1 | 2 | 3 | 4 |5 | 6 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | | | | | |
| 3 | | | | X |X |
| 4 | | | X | | |
| 5 | | | | | |
| 6 | | X | | | end |
这样就拦不住
| 1 | 2 | 3 | 4 |5 | 6 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | | | | | |
| 3 | | | | X |X |
| 4 | | | X | | |
| 5 | | X | | | |
| 6 | | X | | | end |
这样就拦住了
所以不难发现，要想拦住这个娃必须要满足以下几点条件：
$1.$必须与一边相连。
$2.$每一个路标必须在另一个路标的旁边相邻位置，如斜对角线上一格，或相邻格。
$3.$这一连串相邻的路障必须将起点与终点之间的路径截断，否则不能。
#### 然后我们就只需要从边上的路障找起，每一次寻找他的相邻的路障，只要找到了一次能够切断起点和终点的情况，就说明这个孩子走不到终点，如果把边上所有的路障都搜索过了，还没有切断，就说明这个孩子可以走到终点！
#### 那这不就非常美滋滋了，搜索的总量已经缩小的没个人样了。。。
先在还有一个问题就是如何说明这个路障切断了起点和终点
那就分类讨论就行了
可以切断的情况一：（终点所在的一条边与终点所在的另一条边相连）
| 1 | 2 | 3 | 4 |5 | 6 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | start | | | | |
| 3 | | | | X |X |
| 4 | | | X | | |
| 5 | | X | | | |
| 6 | | X | | | end |
可以切断的情况二：（一条边和与其相对的另一条边相连）
| 1 | 2 | 3 | 4 |5 | 6 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | start | | | X | |
| 3 | | | | X | |
| 4 | | | X | | |
| 5 | | X | | | |
| 6 | | X | | | end |
和
| 1 | 2 | 3 | 4 |5 | 6 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | start | | | | |
| 3 | | | | X | |
| 4 | X | | X | | X |
| 5 | | X | | | |
| 6 | | | | | end |
可以切断的情况三：（起点点所在的一条边与起点点所在的另一条边相连）
| 1 | 2 | 3 | 4 |5 | 6 |
| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |
| 2 | start | | | X | |
| 3 | | | | X | |
| 4 | X | | X | | |
| 5 | | X | | | |
| 6 | | | | | end |
这就是所有的情况了，只有以上的三种条件之中的任意一种，才能切断起点和终点！
所以我们可以选择两条边，每一次只要发现有在这两条边上的有效路障，就让他入队。
然后就和一般的广搜思路一模一样了，只要有哪一个路障连到了选择的两条边之外的另外两条边，就走不到终点。（选择的两条边必须相邻）
有一个小技巧，就是我们可以定义两个数组$dx , dy$，来表示这个路障下一次搜索的方向
```
int dx[8]={-1,1,0,0,1,-1,-1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
```
这之后寻找路障（位置 $x$,$y$）就只需要在$x+dx[i] , y+dy[i]$这八个位置就行了
具体操作请见代码：
```
#include<cstdio>
#include<algorithm>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
int a[1010][1010],T,n,x,y;
queue<int> nx;
queue<int> ny;
int dx[8]={-1,1,0,0,1,-1,-1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
bool judge( int xx,int yy )
{
if(xx>=1&&yy>=1&&xx<=n&&yy<=n)
{
if(a[xx][yy]>=1)
{
return true;
}
}
return false;
}
void bfs()
{
while(!nx.empty())
{
int nowx=nx.front();
int nowy=ny.front();
nx.pop();
ny.pop();
if( nowx==n||nowy==1 )
{
printf("No\n");
return ;
}
for(int i=0;i<=7;i++)
{
int nexx=nowx+dx[i];
int nexy=nowy+dy[i];
{
if(judge(nexx,nexy))
{
nx.push(nexx);
ny.push(nexy);
a[nexx][nexy]=0;
}
}
}
}
printf("Yes\n");
return;
}
int main()
{
scanf("%d",&T);
for(int s=1;s<=T;s++)
{
scanf("%d",&n);
int o=2*n-2;
for(int i=1;i<=o;i++)
{
scanf("%d %d",&x,&y);
if( x+y-2 > i )
{
a[x][y]=1;
if(x==1||y==n)
{
nx.push(x);
ny.push(y);
}
}
}
bfs();
memset(a,0,sizeof(a));
}
return 0;
}
```