池塘计数

BFS FloodFill 可以在线性时间复杂度内, 找到某个点所在的连通块。

题目

P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M(1\le N\le 100,1\le M\le 100)$ 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 1 行：两个空格隔开的整数：N 和 M。

第 2 行到第 N+1 行：每行 M 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

样例

输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

3

思路

根据题目样例分析可得, 一个W的周围8个格子都视为连通。可以用循环遍历所有节点, 在第一个为W的节点上进行BFS泛洪标记, 维护一个全局变量res储存当前进行的BFS次数, 该次数就是水坑数量。

代码

const int N = 110;
typedef pair<int, int> PII;
int g[N][N];
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}; // 上下左右 左上 右上 左下 右下
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int n, m;
bool st[N][N];
int res;
 
void bfs(int i, int j)
{
    res++;
    queue<PII> q;
    q.push({i, j});
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        if (st[x][y])
            continue;
        st[x][y] = true;
        for (int i = 0; i < 8; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] && !st[a][b])
            {
                q.push({a, b});
            }
        }
    }
}
 
int main()
{
    cin >> n >> m;
    cin.get();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            g[i][j] = c == 'W';
        }
        cin.get();
    }
#ifdef debug
 
    REPe(i, 1, n)
    {
        REPe(j, 1, m)
        {
            if (g[i][j])
                cout << 'W';
            else
                cout << '.';
        }
        cout << endl;
    }
#endif
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (g[i][j] && !st[i][j])
                bfs(i, j);
        }
    }
 
    cout << res << endl;
    return 0;
}