image.png

BFS求解问题的特点:

image.png

Flood Fill算法

image.png
想象洪水覆盖的过程。
image.png
image.png
image.png
image.png

Flood Fill能用BFS就用BFS，相当于找连通块
image.png

池塘计数问题

image.png

image.png （八连通）统计连通块的个数

城堡问题

image.png


image.png
image.png

找地图中的所有连通块，但是前置背景复杂了一些

image.png二进制表示方块周围墙的情况
image.png

山峰与山谷

判断连通块的类型

image.png

image.png

最短路模型

迷宫问题

image.png
使用Pre数组记录路径

武士风度的牛

抓住那头牛

image.png
特殊的dijisktra算法

多源BFS

image.png
输入：image.png
求每个位置到所有1的距离-曼哈顿距离的最小值
输出： image.png
image.png
多源bfs模型 转 化为 单源bfs模型

最小步数模型

image.png
image.png
使用哈希映射字符串image.png
c++可以使用map，unordered_map
image.png

双端队列广搜

image.png

双向广搜

image.png

image.png
image.png
image.png

用双向广搜提高最小步数问题的运行效率
每次选择两个队列中数量少的那个队列进行扩展。

A*

启发式算法

image.png

重点在于设计估价函数

第k短路