概念

breadth first search(bfs) 宽度优先搜索。算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

这块应该先去了解一下图上的遍历的过程，更好理解代码

棋盘问题，Flood Fill，问题状态的表述升级，模型主要特点，最短路/最少步数/最少次数，就是图论最短路问题，边权是1的情况。

根据下面示例代码，学习bfs()，学会使用queue<>。bfs相对是好写的，模板很清晰。

《一本通》题目

【例8.2】细胞
  1. // Flood Fill
  2. // 示例代码
  3. #include <bits/stdc++.h>
  5. using namespace std;
  7. typedef pair<int, int> PII;
  9. const int N = 1e4 + 10;
  11. char s[N][N];
  12. int n, m; //没有给nm范围
  14. int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
  16. void bfs(int ux, int uy)
  17. {
  18.     queue<PII> q;
  19.     q.push(make_pair(ux, uy));
  21.     while (!q.empty()){
  22.         PII t = q.front(); q.pop();
  23.         int x = t.first, y = t.second;
  24.         s[x][y] = '0';
  26.         for (int i = 0; i < 4; i++){
  27.             int a = x + dx[i], b = y + dy[i];
  28.             if (a < 0 || a >= n || b < 0 || b >= m) continue;
  29.             if (s[a][b] == '0') continue;
  31.             q.push(make_pair(a, b));
  32.         }
  33.     }
  34. }
  36. int main()
  37. {
  38.     cin >> n >> m;
  39.     for (int i = 0; i < n; i++) scanf("%s", s[i]);
  41.     int cnt = 0;
  42.     for (int i = 0; i < n; i++)
  43.         for (int j = 0; j < m; j++){
  44.             if (s[i][j] != '0'){
  45.                 bfs(i, j);
  46.                 cnt++;
  47.             }
  48.         }
  50.     cout << cnt << '\n';
  52.     return 0;
  53. }

【例8.3】最少步数
  1. //棋盘问题，最短路

Dungeon Master
  1. //棋盘问题，最短路

Lake Counting
  1. //Flood Fill

The Castle
  1. //Flood Fill，位运算

仙岛求药
  1. //棋盘问题，最短路，多组测试数据

走迷宫
  1. //棋盘问题，最短路，一组测试数据

抓住那头牛
  1. //最短路问题，问题空间转换为数轴上运动

走出迷宫
  1. //棋盘问题，最短路

迷宫问题
  1. //棋盘问题，打印路径

献给阿尔吉侬的花束
  1. //棋盘问题，最短路，T组数据

Knight Moves
  1. //棋盘问题，最短路，8个方位

《517》题目

拼图游戏
  1. //对拼图的编码，解码，开哈希，移动拼图的模拟。此题能够独立写出来，标志这bfs过关

类似的题目有：

洛谷：八数码难题, acwing：AcWing 845. 八数码

营救计划
  1. //迷宫问题，遇到守卫还是道路分类讨论

倒酒
  1. //锻炼问题状态的理解，三个酒杯的状态表述，模拟三个酒杯互相倒酒的枚举过程。一道好题。