一、概述

基本的搜索一般分为bfs和dfs，在都可行的前提下，最好选择bfs，因为dfs递归时可能会爆栈，而且bfs的思路和过程可能会清晰一些因为不用递归，一般是维护队列就行

1、Flood Fill算法

思路：

具体过程就是将符合条件的点入队,然后依次遍历这个点的几个方向,判断新的点是否满足条件,满足的话就入队继续更新。

2、最短路模型

bfs可以解决一些最短路的问题,前提是当所有边的距离相同时才行
基本只用遍历一次,从起点开始，第一次遍历到终点就结束，中间过程可能会记录一些值，比如走过的路径，最短路的长度等等，多开一个数组来记录就行，有些还可以和状态st数组合并，有值就代表走过。

粘一个例题代码：acwing1076,https://www.acwing.com/problem/content/1078/

3、多源BFS

所谓多源，就是有好几个起点的BFS，但是我们可以改进成一个单源最短路问题，也就是常见的那种，我们可以认为有一个虚拟源点，它与我们当前的每个起点都有一条权为0的边，这样我们就可以看成一个起点的BFS了。
当然真正写的时候我们不需要把虚拟源点写出来，我们之前BFS遍历不是把所有和这个点相关的点都入队吗？所以这里我们可以直接将所有起点入队就行了。就改进成一个单源DFS问题

粘一个样例代码：acwing173,https://www.acwing.com/problem/content/description/175/

4、最小步数模型

将一个矩阵或者其他的当成是一个点，要求我们将这个点的状态转变成结果状态的最少操作次数
这个类型也是我目前遇到搜索最麻烦的题了(太菜了hhh)，
一般可以把矩阵什么的转换成字符串或者用哈希表来存，便于表示状态，其实思路不是特别难，就是加上这个转化过程，还有题干上要求的操作，会非常麻烦。

粘一下例题代码：acwing1107，https://www.acwing.com/problem/content/1109/

思路：

5、双端队列BFS

概述：

一开始我以为的双端队列是起点和终点分别开个队列进去找，然后找第一次碰头的点算出来距离(hhh)
双端队列BFS适用于图中只存在0，1两种权的边，在队列中每次通过队头更新出的所有点中，如果是小的点(0)插入队头，大的点(1)插入队尾（当然如果你找的是最长路就应该反过来），
原理是为了维护两段性和单调性，保证每次找的是最短路，也可以看成是一种特殊的Dijkstra算法。

例题：

粘一下例题代码：acwing175，https://www.acwing.com/problem/content/177/

思路：

用STL中的deque开一个双端队列，每次用出队的点遍历四个方向，如果找到了一个没有确定最短路的点，而且当前点可以更新这个点的最短距离时，边为1就入到队尾，边为0就入到队头，保证两段性和单调性。

6、双向广搜——对最小步数模型的优化

概述

双向广搜优化一般只适合最小步数模型，要已知起点终点，开两个队列，一个从起点开始走一个从终点开始走。
双向广搜的优点：由于正常的BFS每往下搜索一次，状态就会指数型增加，当数据范围较大时很容易TLE或者MLE，比如一共10步，每步有6个选择，最坏情况下是6^10 级别。但如果我们从起点终点同时搜，就可以变成2*6^5级别。

例题

粘一下例题代码：acwing190,https://www.acwing.com/problem/content/192/