1.BFS

·求最小问题
·基于迭代（不会爆栈）

模型一：Flood Fill 算法

在线性的时间找到某个点的连通块
1097. 池塘计数
 池塘计数题解

1098. 城堡问题
 城堡问题题解

1106. 山峰和山谷
 山峰和山谷题解

模型二：最短路模型

1076. 迷宫问题
 迷宫问题题解

188. 武士风度的牛
 武士风度的牛题解

1100. 抓住那头牛
 抓住那头牛题解

模型三：多源 BFS

173. 矩阵距离
 矩阵距离题解

2022-4-29 打卡

模型四：最小步数模型

1107. 魔板
 魔板题解

模型五：双端队列广搜

将权值为 0 存入对头，权值为 1 存入队尾
175. 电路维修
 电路维修题解

模型六：双向广搜

作者：yxc
(BFS,双向 BFS) O((LN)5)O((LN)5)
假设每次决策数量是 KK，那么如果直接 BFS，最坏情况下的搜索空间是 K10K10，非常大，所以会 TLE 或者 MLE。

如果采用双向 BFS，则可以把搜索空间降到 2K52K5。在实际测试中只需 20ms 左右，剪枝效果很好。

BFS 的扩展方式是：分别枚举在原字符串中使用替换规则的起点，和所使用的的替换规则。

时间复杂度
假设字符串长度是 LL，替换规则一共有 NN 个，则：

在最坏情况下每次会从字符串的每个位置开始，使用全部的 NN 种替换规则，因此总共会有 LNLN 种扩展方式，从起点和终点最多会分别扩展 5 步，因此总搜索空间是 2(LN)52(LN)5。

在 BFS 过程中，空间中的每个状态只会被遍历一次，因此时间复杂度是 O((LN)5)O((LN)5)。

190. 字串变换
 字串变换题解

模型七：A*

麻了，没太明白，先放一下，最后回来解决
大佬写的真好，从广搜到 Dijkstra 的算法到 A*算法A*算法简介
 178. 第 K 短路

179. 八数码

2.DFS

模型一：DFS 之连通性模型

1112. 迷宫
 迷宫题解

1113. 红与黑
n 和 m 是真的恶心
红与黑题解

2022-4-30 打卡

模型二：DFS 之搜索顺序

1116. 马走日
 马走日题解

1117. 单词接龙
 单词接龙题解

1118. 分成互质组
 分成互质组题解

2022-5-1 打卡