Flood Fill 连通块

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 1179 字

从一个点扩散同色区域，统计连通块

搜索
Flood Fill

前置内容

BFS · 迷宫最短路

正文

// Flood Fill：连通块计数
// 从一个点扩散同色区域
// BFS / DFS 逐格访问
// 例：统计图中连通块个数
#include <cstdio>
char g[105][105];
int vis[105][105], n, m, ans = 0;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
// 从 (x,y) 出发填色
void bfs(int x, int y) {
    int qx[10005], qy[10005], h = 0, t = 0;
    // 起点入队并标记
    qx[t] = x; qy[t] = y; vis[x][y] = 1;
    t++;
    while (h < t) {
        int cx = qx[h], cy = qy[h]; h++;
        // 四方向扩展
        for (int k = 0; k < 4; k++) {
            int nx = cx + dx[k],
                ny = cy + dy[k];
            // 越界或已访问跳过
            if (nx < 1 || ny < 1) continue;
            if (nx > n || ny > m) continue;
            if (vis[nx][ny]) continue;
            // 同块则入队
            vis[nx][ny] = 1;
            qx[t] = nx; qy[t] = ny; t++;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf(" %c", &g[i][j]);
    // 未访问的格子起新块
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j]) {
                bfs(i, j);
                // 每发现一块计数 +1
                ans++;
            }
    printf("%d", ans);
    return 0;
}

Flood Fill 连通块

前置内容

正文

CSP-J · 编程模板的其它内容