AT896 【幅優先探索】 题解

**（前排提醒：如果你本地全过提交全错，不妨检查一下是否输出了换行）** ~~AtCoder特色~~ [题目链接：AT896 幅優先探索](https://www.luogu.com.cn/problem/AT896) 从题目上可以看出，这是一道非常简单的广度优先搜索（$BFS,\ Breadth\ First\ Search$）模板题。 广度优先搜索的基本思想是什么呢？假设所有可能出现的情况是一棵树，那么广度优先搜索就是从根结点开始，先搜索完根节点**所有的深度等于自身深度+1的子结点**，再搜索每个子结点的子结点，当一个点的所有深度等于自身深度+1的子结点都被搜索完后，才会搜索下一个结点的子结点。 而深度优先搜索（$DFS,\ Depth\ First\ Search$）则是从根结点开始，搜索根节点的第一个子结点，然后搜索这个子结点的第一个子结点……**直到搜索到叶节点后，再“回溯”**，搜索他的父节点的下一个子结点。 换句话说，以下面这棵树为例子， 广度优先搜索的搜索顺序是$A\rightarrow B\rightarrow C\rightarrow D\rightarrow E\rightarrow F\rightarrow G\rightarrow H\rightarrow I$ 而深度优先搜索的搜索顺序则是$A\rightarrow B\rightarrow D\rightarrow E\rightarrow I\rightarrow C\rightarrow F\rightarrow G\rightarrow H$  那么如何实现广度优先搜索算法呢？我们需要用到**队列**。开始搜索时先将根结点入队**并将根结点标记为已被搜索过**，然后开始循环，只要队列非空且没有到达终点，就将当前搜索到的结点的**符合条件且未被搜索过**的子结点入队。以下是伪代码： ```cpp 起点入队; 将起点标记为已被搜索过; while(队列非空) { if(到达终点) { 输出结果; return 0; } if(子结点符合条件且未被搜索过) { 子结点入队; 将子结点标记为已被搜索过： } 当前队首元素出队; } ``` 还是以上面那棵树为例子，那么操作顺序就是： $A$入队并标记$A\quad\rightarrow\quad$搜索$A\quad\rightarrow \quad B$、$C$入队并标记$B$、$C\quad\rightarrow\quad$搜索$B\quad\rightarrow \quad D$、$E$入队并标记$D$、$E\quad\rightarrow \quad$搜索$C\quad\rightarrow \quad F$、$G$、$H$入队并标记$F$、$G$、$H\quad\rightarrow\quad$搜索$D\quad\rightarrow \quad$搜索$E\quad\rightarrow \quad I$入队并标记$I\quad\rightarrow\quad$搜索$F\quad\rightarrow\quad$搜索$G\quad\rightarrow\quad$搜索$H$ 由于STL中的队列常数较大，效率较低，所以我们可以尝试手写队列，这是我经常用的一种比较简单的队列写法（注意不同题目的队列写法不同）： ```cpp int Head=0,Tail=0; //队列的头指针和尾指针 struct point { int Y,X,Step;//Y和X为坐标，Step为到达该点需要的步数 }Queue[1000];//空间可以稍微开大一些 inline void Push(int y,int x,int step)//入队操作 { Queue[Tail].Y=y;//元素从队尾进入 Queue[Tail].X=x; Queue[Tail].Step=step; ++Tail;//尾指针+1 if(Tail==1000) { Tail=0;//实现队列空间的重复利用：如果尾指针超过了队列的范围，则重新变为0。可以利用这个方法将链状的队列变为环状的队列 } return ; } inline void Pop()//出队操作 { ++Head;//头指针+1（因为如果队列的同一个位置被重复使用，后面入队的元素可以直接覆盖原有的元素，所以可以不必初始化该位置） if(Head==1000) { Head=0;//同上 } return ; } inline bool Empty()//判断队列是否为空 { return Head==Tail?1:0;//如果头指针=尾指针，说明队列为空 } ``` 入队和标记的操作可以封装成一个`BFS()`函数： ```cpp /*R和C为题目给出的数据，Visited[][]是用来标记每个坐标是否已被搜索过的bool型数组*/ inline void BFS(int y,int x) { if(y>=1&&y<=R&&x>=1&&x<=C&&Square[y][x]=='.'&&Visited[y][x]==0)//判断坐标是否越界、该坐标是否允许行走、该坐标是否被搜索过 { Push(y,x,SS+1);//该坐标入队 Visited[y][x]=1;//同时将该坐标标记为已被搜索过 } return ; } ``` 在这道迷宫问题中，每个结点的子结点就是每个方格的上下左右四个方格。则主函数中搜索部分的内容为： ```cpp /*个人习惯，先对队首元素的表示方式进行预处理，方便代码的书写*/ #define YY Queue[Head].Y #define XX Queue[Head].X #define SS Queue[Head].Step int main() { /*起点入队，同时将起点标记为已被搜索过*/ Push(sy,sx,0); Visited[sy][sx]=1; /*如果队列不空，就一直进行搜索*/ while(!Empty()) { /*判断当前队首坐标是否为终点，如果是则直接输出答案，结束程序*/ if(YY==gy&&XX==gx) { cout<<SS<<endl; return 0; } /*搜索队首坐标的上下左右四个点*/ BFS(YY-1,XX);//上 BFS(YY+1,XX);//下 BFS(YY,XX-1);//左 BFS(YY,XX+1);//右 Pop();//队首元素出队 } return 0; } ``` 附上完整AC代码（注意：如果用scanf读入字符，可能会错误地读入换行符）： ```cpp #include <iostream> using namespace std; /*个人习惯，先对队首元素的表示方式进行预处理，方便代码的书写*/ #define YY Queue[Head].Y #define XX Queue[Head].X #define SS Queue[Head].Step /*题目给出的数据*/ int R,C,sy,sx,gy,gx; char Square[51][51]; /*还需要一个Visited数组来判断一个坐标是否已经被搜索过*/ bool Visited[51][51]={}; /*因为STL中的队列常数较大，所以可以自行手写队列（介绍一种简单的队列写法）*/ int Head=0,Tail=0; //队列的头指针和尾指针 struct point { int Y,X,Step;//Y和X为坐标，Step为到达该点需要的步数 }Queue[1000];//空间可以稍微开大一些 inline void Push(int y,int x,int step)//入队操作 { Queue[Tail].Y=y;//元素从队尾进入 Queue[Tail].X=x; Queue[Tail].Step=step; ++Tail;//尾指针+1 if(Tail==1000) { Tail=0;//实现队列空间的重复利用：如果尾指针超过了队列的范围，则重新变为0。可以利用这个方法将链状的队列变为环状的队列 } return ; } inline void Pop()//出队操作 { ++Head;//头指针+1（因为如果队列的同一个位置被重复使用，后面入队的元素可以直接覆盖原有的元素，所以可以不必初始化该位置） if(Head==1000) { Head=0;//同上 } return ; } inline bool Empty()//判断队列是否为空 { return Head==Tail?1:0;//如果头指针=尾指针，说明队列为空 } /*广度优先搜索函数*/ inline void BFS(int y,int x) { if(y>=1&&y<=R&&x>=1&&x<=C&&Square[y][x]=='.'&&Visited[y][x]==0)//判断坐标是否越界、该坐标是否允许行走、该坐标是否被搜索过 { Push(y,x,SS+1);//该坐标入队 Visited[y][x]=1;//同时将该坐标标记为已被搜索过 } return ; } int main() { /*这句话可以关闭iostream与stdio的同步流，从而提高cin和cout的效率*/ ios::sync_with_stdio(0); /*输入数据*/ cin>>R>>C>>sy>>sx>>gy>>gx; for(int i=1;i<=R;++i) { for(int j=1;j<=C;++j) { cin>>Square[i][j]; } } /*起点入队，同时将起点标记为已被搜索过*/ Push(sy,sx,0); Visited[sy][sx]=1; /*如果队列不空，就一直进行搜索*/ while(!Empty()) { /*判断当前队首坐标是否为终点，如果是则直接输出答案，结束程序*/ if(YY==gy&&XX==gx) { cout<<SS<<endl; return 0; } /*搜索队首坐标的上下左右四个点*/ BFS(YY-1,XX);//上 BFS(YY+1,XX);//下 BFS(YY,XX-1);//左 BFS(YY,XX+1);//右 Pop();//队首元素出队 } return 0; } ``` $BurningEnderDragon\quad 2021.02.02$