填涂颜色

题意

方阵中的 1 形成闭合边界。把无法只经过 0 到达矩阵边界的内部零改成 2，其余数字不变。

思路

直接从每个零判断能否到边界会重复搜索。反过来，从矩阵外部出发，把所有与外界连通的零一次找完；剩下的零恰好被 1 包围。

给原矩阵补一圈零后，外界统一成一个起点 (0,0)。BFS 把外部零标成 -1。输出原区域时：仍为 0 的改成 2，-1 恢复成 0，1 保持不变。

思路二：两次 BFS

标准做法是从外向内一次 BFS 标记外部区域。下面换一种写法：从每个 0 区域判断能不能走出去，能走出的保留，走不出的填涂。

第一次 BFS：从当前 0 格子出发，用独立的 vis[][] 遍历整个连通分量。如果该区域有格子位于矩阵边界，说明能走出去（外部区域）；否则说明被 1 包围（内部闭合圈）。
第二次 BFS：判定为内部闭合圈后，再做一次 BFS，把整个区域的 0 改为 2。

这样"正难则反"的思路被拆成正向判断 + 条件执行，逻辑上更直观。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114/**
 * 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-07-28 17:27
 * update_at: 2026-07-28 17:27
 */
// main2.cpp：两次 BFS。第一次判断 0 区域能否走到边界，第二次把内部闭合圈填为 2。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n;
int g[MAXN][MAXN];    // 0: 未访问, 1: 墙, 2: 内部填涂
bool vis[MAXN][MAXN]; // BFS1 专用访问标记
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// BFS1：从 (sx,sy) 出发探索整个 0 区域，不修改 g。
// 判断该区域能否走到矩阵边界（能不能走出去）。
// 返回 true 表示能走出去（外部区域），false 表示被包围（内部区域）。
bool bfs1(int sx, int sy) {
    if (g[sx][sy] != 0 || vis[sx][sy])
        return false;

    bool can_get_out = false;
    queue<pair<int,int>> q;
    q.push({sx, sy});
    vis[sx][sy] = true;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 当前格子位于矩阵边界，说明可以走出去
        if (x == 1 || x == n || y == 1 || y == n)
            can_get_out = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > n)
                continue;
            if (vis[nx][ny] || g[nx][ny] != 0)
                continue;
            vis[nx][ny] = true;
            q.push({nx, ny});
        }
    }
    return can_get_out;
}

// BFS2：从 (sx,sy) 出发 flood fill，把整个内部闭合圈改为 2
void bfs2(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    g[sx][sy] = 2;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > n)
                continue;
            if (g[nx][ny] != 0)
                continue;
            g[nx][ny] = 2;
            q.push({nx, ny});
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == 0 && !vis[i][j]) {
                // BFS1：判断这个 0 区域能不能走出去
                if (!bfs1(i, j)) {
                    // 不能走出去 → 内部闭合圈，BFS2 填涂为 2
                    bfs2(i, j);
                }
                // 能走出去 → 外部区域，不做处理（保留 0）
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == 1)
                cout << 1 << " ";
            else if (g[i][j] == 2)
                cout << 2 << " ";
            else
                cout << 0 << " ";
        }
        cout << "\n";
    }
    return 0;
}

Python 知识

[[0]*(n+2)] 和列表推导式组合出带边框矩阵；每个输入行用 [0,*map(...),0] 解包插入左右边框。
补边让四方向搜索无需分别枚举原矩阵四条边。
输出生成器 2 if value==0 else max(value,0) 同时完成三种值映射。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：安全创建二维列表。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque BFS。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20from collections import deque


n = int(input())
grid = [[0] * (n + 2)]
grid += [[0, *map(int, input().split()), 0] for _ in range(n)]
grid += [[0] * (n + 2)]

grid[0][0] = -1
queue = deque([(0, 0)])
while queue:
    x, y = queue.popleft()
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nxt_x, nxt_y = x + dx, y + dy
        if 0 <= nxt_x < n + 2 and 0 <= nxt_y < n + 2 and grid[nxt_x][nxt_y] == 0:
            grid[nxt_x][nxt_y] = -1
            queue.append((nxt_x, nxt_y))

for row in grid[1:n + 1]:
    print(*(2 if value == 0 else max(value, 0) for value in row[1:n + 1]))

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://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1162 填涂颜色 */
/* 给矩阵补一圈 0 并从外部 BFS，未被搜索到的 0 就是闭合圈内部。 */

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

const int MAXN = 35;

int n;
int g[MAXN][MAXN]; // 原矩阵，外围补一圈 0
int vis[MAXN][MAXN]; // 标记外部可达的 0
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    vis[0][0] = 1;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx > n + 1 || ny < 0 || ny > n + 1) continue;
            if (vis[nx][ny]) continue;
            if (g[nx][ny] == 1) continue; // 墙不能通过
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

int main() {
    cin >> n;
    // 读入矩阵，外围自动补一圈 0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

    bfs(); // 从外部 bfs，标记所有外部可达的 0

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][j] == 1) {
                cout << 1 << " ";
            } else if (vis[i][j]) {
                cout << 0 << " "; // 外部可达，保持 0
            } else {
                cout << 2 << " "; // 内部闭合圈，填 2
            }
        }
        cout << "\n";
    }
    return 0;
}

复杂度

BFS 与输出各扫描常数次矩阵，时间和空间复杂度均为 $O(n^2)$ 。

总结

“找被包围区域”通常适合正难则反：先从边界找出所有外部区域，未被访问的部分自然就是内部。

目录

题意

思路

思路二：两次 BFS

Python 知识

代码

复杂度

总结