做了那么多 BFS

写了那么多shit

今天，亲爱的@让我写一个 BFS 题型题单

那么，请拿上来自nPr123f的免费车票，一起往下翻~

BFS题型大类介绍及题单

BFS 代码框架

queue <State> q;
q.push(初始状态);
vis[初始状态] = true;

while (!q.empty()) {
  State st = q.front();
  q.pop();

  for (枚举所有可扩展状态) {
    if (状态合法 && !vis[扩展状态]) {
      q.push(扩展状态);
      vis[扩展状态] = true;
    }
  }
}

题型 1：遍历（找连通块/可达性）

连通块

814 A1329. 【例8.2】细胞
zxoj链接

735 A1250. The Castle ⭐
zxoj链接

题型 2：最短路问题

815 A1330. 【例8.3】最少步数
zxoj链接

737 A1252. 走迷宫
zxoj链接

738 A1253. 抓住那头牛
zxoj链接

845 A1360. 奇怪的电梯(lift)
zxoj链接

992 P1825. 【USACO11OPEN】 Corn Maze S
zxoj链接
luogu链接

995 P8693. 【蓝桥杯 2019 国 AC】 大胖子走迷宫
zxoj链接
luogu链接

记录前序节点的最短路
740 A1255. 迷宫问题
zxoj链接
luogu链接

单源点、多终点
990 P1364. 医院设置
zxoj链接
luogu链接

多源点、多终点
1018 A1474. 矩阵距离
zxoj链接

加状态记录的最短路

（思想类DP，局部最优不代表全局最优）
994 P3818. 小A和uim之大逃离 II
zxoj链接
luogu链接