刷题随笔
$BFS$
广度优先搜索
$Flood Fill$
可以在线性时间复杂度内,找到某个点所在的连通块。
AcWing 1097.池塘计数
AcWing 1098.城堡问题
AcWing 1106.山谷和山峰
AcWing 3371.舒适的奶牛
最短路模型
可以在线性的时间复杂度内,找到所有点到起点的最短距离(所有边权相等)。
AcWing 1076.迷宫问题
AcWing 188.武士风度的牛
AcWing 1100.抓住那头牛
多源BFS
解决多个起点bfs的问题,可以通过建立虚拟源点的方式,可以将多源 BFS转换为单源 BFS问题。
AcWing 173.矩阵距离
最小步数模型
把当前状态变为目标状态的最小步数。
AcWing 1107.魔板
双端队列广搜
主要解决图中边的权值只有0或者1的最短路问题。当前可以扩展到的点的边权为0时,将其加入队首;边权为1时,将其加入队尾。
AcWing 175.电路维修
双向广搜
从起点和终点同时开始搜索,当两个搜索相遇时结束搜索.