搜索（5）

深度优先搜索一般是递归实现的，搜索过程中总是优先遍历当前节点的子节点。从这一节开始，我们将学习广（宽）度优先搜索

这个 GIF 图中，节点被染成绿色的顺序表示在宽度优先搜索过程中节点被访问的顺序。可以看到从根节点开始访问，每当一层的节点都被访问过后，下一层的节点才会开始被访问。接下来我们对整个过程进行更详细的分解：

1. 在搜索的第一步，访问根节点，即是节点 1。由于该层只有节点 1 这一个节点，因此只能访问它
   在访问节点 1 时，我们发现根节点有 2 个儿子节点，分别是节点 2 和节点 3，于是将这 2 个儿子节点记录下来
2. 完成了第一层的访问后，根据记录我们知道该图中还存在有节点 2 和节点 3，即第二层的 2 个节点。它们到根节点的距离为 1。于是依次访问这两个节点，同时在访问时，我们发现了节点 2 的儿子节点 4 和 5，以及节点 3 的儿子节点 6 和 7，将这 4 个节点记录下来
3. 当完成第二层的访问后，继续根据记录来依次访问节点 4~7，也对应了图中的第三层节点。在这一层中包含有 4 个节点，均是第二层节点的子节点，他们到根节点的距离均为 2。由于这些节点都不包含有子节点，不会再增加记录的节点数量，因此访问完成后退出搜索

在上面的过程中我们发现以下两个事实：

• 广度优先搜索的顺序与子节点到初始节点的距离有关，离初始节点越近的子节点会更早被访问。
  在 Gif 的例子中，越靠近上方的层离根的距离越近，因此总是会比下层的节点先访问
• 若将初始节点记作记录的第一个节点，记录节点的顺序对应的正是节点被访问的顺序。
  而先被记录的节点会优先访问，这正好和队列先进先出的性质相符，因此可以使用队列来模拟这一过程

在访问的过程中，由于我们访问一个节点之后，会记录它的子节点。当该层的节点全部完成访问后，才会根据记录依次访问下一层节点。这样也导致同一层节点会集中在记录序列中的一个连续区间内。根据前面所描述的过程我们可以得到广度优先搜索的流程：

1. 建立队列数据结构，并将初始访问的节点加入队列
2. 依次从队列头弹出节点，进行访问，并将其子节点加入到队列末尾

看下面一段代码段

int que[MAXN];//用于记录的队列，这里用数组来模拟
bool inq[MAXN];//记录一个节点是否在队列中
int head = 0,tail = 0;//当前队列的头尾指针
que[tail++] = root;//根节点入队
inq[root] = true;
while(head < tail)//若队列内仍有元素
{
    int u = que[head++];//取出队首元素
    visit(u);//访问该节点
    for(int j : g[u])//枚举所有u的子节点
    {
       if(!inq[j])//如果j不在队列中
       {
           que[tail++] = j;//将子节点加入队列中
           inq[j] = true;
       }
    }
}

在这段代码中，我们定义了两个数组，分别是记录节点的 que 数组和一个布尔类型的数组 inq。que 数组和变量 head、tail 用来模拟队列的数据结构，当然你也可以直接使用 C++STL 中的 queue 容器。inq 的目的是为了记录哪些节点已经在队列中了，防止重复的将某些节点加入队列中而产生的错误

初始化时，我们将搜索的起始节点加入队列，同时标记它已经被加入队列中。如果还有其他需要初始化的内容，也需要在这里执行。
接下来是 while 循环，在满足队列不为空的情况下，反复从队列中取出头元素进行访问。访问这个过程具体要做哪些工作是由题目要求决定的。同时在访问一个节点完成后，需要将其子节点也加入到队列之中。当所有的节点均被访问之后，即队列为空时，则会自动跳出该循环

以上就是宽度优先搜索实现的一个基本框架。下图演示了在一张图上 BFS 的过程：

蓝色方格代表队列，左边一段是已经移出队列的节点，右边是当前队列，红色箭头是首尾指针。白色节点代表还没访问到的节点，灰色节点是在队列中的节点，黑色节点是已经被移出队列的节点。广度优先搜索保证了每个节点只会进入队列一次，离开队列一次。因此假设节点数量为 n，边数为 m 时，广度优先搜索的基础时间复杂度为 $O (n+m)$。但和深度优先相比，由于需要利用 que 数组记录访问的节点，所以会有额外 $O (n)$ 的空间开销。在广度优先搜索的过程中，如果节点之间的边的长度都为 1，那么当一个节点被访问时所记录的路径长度一定是根到它的最短路径。这是利用广度优先搜索中最重要的性质。举个例子：

在该例子中，初始节点为 1，我们想要知道到达 3 的最短路径。若我们利用深度优先搜索，则第一次访问到 3 时，路径可能为 1->2->3，不是 1 到 3 的最短路径。而利用宽度优先搜索，第一次扩展时就能够直接找到 1->3 的最短路径，不需要花费额外的时间去访问 1->2->3 的路径。利用这个性质我们就可以完成一些单源点查询最短路径的问题。下面我们就看一道这样的问题：
该题目就是一道典型的利用宽度优先搜索，查询最短路径的问题。根据题目描述，我们可以知道以下几个信息：

• 该图中需要搜索的节点为格子，我们用坐标 [x,y] 来表示格子
• 若将相邻格子的距离视为 1，搜索目标为 [1,1] 到 [n,m] 的最短路径
• 墙壁的格子是不能进入的，因此在搜索过程中需要进行判定
• 在搜索过程中，我们需要记录起始点到达该节点的步数

根据上面的信息，我们需要使用到下面这些数据结构：

int que[MAXN*MAXN][2];//第二维度为2，因为要记录x,y两个坐标值
int steps[MAXN][MAXN];//记录到达[x,y]的步数
bool inq[MAXN][MAXN];//记录[x,y]是否被访问过

BFS 的代码如下：

//方向数组，分别表示上下左右四个方向移动时，坐标的增量
const int dr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int head = 0,tail = 0;
que[tail][0] = 1;
que[tail][1] = 1;
steps[1][1] = 0;
inq[1][1] = true;
tail++;
while(head > tail)
{
    int x = que[head][0];
    int y = que[head][1];
    head++;
    for(int d = 0;d < 4;d++)
    {
        int nx = x + dr[d][0];
        int ny = y + dr[d][1];
        //保证[nx,ny]在地图内
        if(inMap[nx][ny] && !inq[nx][ny] &&
           map[nx][ny] != '#')
        steps[nx][ny] = steps[x][y] + 1;
        inq[nx][ny] = true;
        que[tail][0] = nx;
        que[tail][1] = ny;
        tail++;
    }
}

程序一开始的 dr [] 数组起到的作用与之前讲过的 DFS 中的 dx [] 和 dy [] 一样，用于表示上下左右 4 个方向

在该问题中，我们同样先将初始节点加入队列，再在队列不为空的情况下反复进行节点的扩展，最后完成搜索。由于题目中的 ` 地图是有限制的矩形区域，因此我们需要额外的 inMap 函数进行位置的辅助判定

同时还需要检查移动到的节点是否为墙壁，当整个搜索完成后，stepsx 中记录的是从 [1,1] 到达 [x,y] 的最少步数，因此 stepsn 也就是问题的答案