【例65.3】 细胞个数

解题思路

把每个符合条件的格子视为图顶点，相邻格子连边。逐格扫描，遇到未访问的目标格就新计一个连通块，并用BFS标记整块。本题仅上下左右四方向连通。

正确性说明

一次BFS恰好访问起点所在连通块的全部格子，且不会访问其他块；访问后不再作为新起点，所以每块恰计一次。

易错点

入队时立即标记，避免同一格重复入队。

复杂度

时间O(nm)，空间O(nm)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &s : a)
        cin >> s;
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] != '0') {
                ans++;
                queue<pair<int, int>> q;
                q.push({i, j});
                a[i][j] = '0';
                while (!q.empty()) {
                    auto p = q.front();
                    q.pop();
                    for (int dx = -1; dx <= 1; dx++)
                        for (int dy = -1; dy <= 1; dy++) {
                            if (abs(dx) + abs(dy) != 1)
                                continue;
                            int x = p.first + dx, y = p.second + dy;
                            if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '0') {
                                a[x][y] = '0';
                                q.push({x, y});
                            }
                        }
                }
            }
    cout << ans << "\n";
    return 0;
}