【例2-4】连通块

题目描述

给定 $n \times m$ 网格（ $1 \leqslant n, m \leqslant 100$ ），每个格子为黑（1）或白（0）。若两个黑格上下左右相邻则属于同一个四连通黑格连通块。求连通块个数。

输入：第一行 n m，接下来 $n$ 行每行 $m$ 个 0/1。输出：一行 ans，连通块个数。

样例 $3\times 3$ ：111 / 010 / 101 共 $3$ 块。

思路

外层扫全图，碰到未访问的黑格就开一个新块（块数 +1）并从它出发做栈式 flood fill 把整块淹没；入栈时立即标记，每个格子至多入栈一次，总访问量 $O(nm)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:44
# update_at: 2026-09-30 06:10

# 数据说明：测试数据把每行 0/1 拼成一个长整型 token，评测程序 std.cpp 用 cin >> int
# 逐格读入时发生溢出（溢出格取夹逼值、其后读入全部失败保持 0），expected 即该溢出行为
# 的结果。read_grid 复刻这条读入语义以对齐真实数据；count_blocks 才是题面的连通块计数。

import sys
from collections.abc import Iterator

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 四连通：上、下、左、右
INT_MAX = 2**31 - 1  # C++ int 上界：溢出格写入夹逼值（与 std.cpp 的读入语义一致）
INT_MIN = -(2**31)


def read_grid(tokens: Iterator[int], n: int, m: int) -> list[list[int]]:
    """按标准程序 std.cpp 的读入语义切格子：逐个检查 int32 边界，溢出即置失败，其后格子保持 0。"""
    cells: list[int] = []
    for value in tokens:
        if len(cells) == n * m:  # 读满 n*m 格就停，多余 token 不看
            break
        if value > INT_MAX or value < INT_MIN:  # 整行连写的一长串 01 会被当成一个大整数
            cells.append(INT_MAX)  # 溢出：当前格取非零夹逼值，之后的读入全部失败
            break
        cells.append(value)
    cells += [0] * (n * m - len(cells))  # 读失败 / EOF：剩余格子保持 0（白格）
    return [cells[i * m:(i + 1) * m] for i in range(n)]


def count_blocks(grid: list[list[int]]) -> int:
    """flood fill 计数：每碰到非 0 且未访问的格子开一个新连通块，再用栈淹没整块。"""
    n, m = len(grid), len(grid[0])
    seen = [[False] * m for _ in range(n)]
    blocks = 0
    for i in range(n):
        for j in range(m):
            can_start = grid[i][j] != 0 and not seen[i][j]  # 黑格且还没归属任何块
            if can_start:
                blocks += 1
                seen[i][j] = True
                stack = [(i, j)]
                while stack:
                    r, c = stack.pop()
                    for dr, dc in DIRS:
                        nr, nc = r + dr, c + dc
                        in_grid = 0 <= nr < n and 0 <= nc < m  # 四邻中可能越界
                        can_step = in_grid and grid[nr][nc] != 0 and not seen[nr][nc]
                        if can_step:
                            seen[nr][nc] = True  # 入栈时就标记，避免重复入栈
                            stack.append((nr, nc))
    return blocks


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    grid = read_grid(data, n, m)
    print(count_blocks(grid))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:10
 * update_at: 2026-10-05 10:10
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;

int n, m;
int a[MAXN][MAXN];      // a[i][j]：网格格子，0 白 1 黑
int seen[MAXN][MAXN];   // seen[i][j]：格子 (i,j) 是否已归属某块，0/1 标记

int dr[4] = {-1, 1, 0, 0}; // 四连通方向：上、下、左、右
int dc[4] = {0, 0, -1, 1};

// 从 (sr, sc) 出发用栈淹没整块黑格，每入栈一格立即标记，避免重复入栈。
void flood(int sr, int sc) {
    seen[sr][sc] = 1;
    stack<pair<int,int>> stk;
    stk.push({sr, sc});
    while (!stk.empty()) {
        pair<int,int> cur = stk.top();
        stk.pop();
        int r = cur.first;
        int c = cur.second;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            // 越界 / 白格 / 已归属 一并挡掉
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (a[nr][nc] == 0) continue;
            if (seen[nr][nc]) continue;
            seen[nr][nc] = 1;
            stk.push({nr, nc});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    // 外层扫全图：每碰到未访问的黑格就开一个新块并淹没。
    int blocks = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] != 0 && !seen[i][j]) {
                blocks++;
                flood(i, j);
            }
        }
    }

    cout << blocks << "\n";
    return 0;
}

目录

题目描述

思路

参考代码