概念

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. }