填涂颜色

形式化题目

给定一个 $n \times n$ 的 0/1 方阵，其中 1 构成一个闭合圈。一个 0 在闭合圈内，当且仅当从它出发只沿上下左右移动、且只经过 0，无法到达方阵边界。

要求把闭合圈内的所有 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/**
 * 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-08-13 13:30
 * update_at: 2026-08-13 13:31
 */
// brute.cpp：小数据暴力解，直接按题意对每个 0 判断能否走到矩阵边界，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n;
int g[MAXN][MAXN];    // 原矩阵
bool vis[MAXN][MAXN]; // 每次判断独立使用，标记本轮访问过的 0
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// 从 (sx,sy) 出发只走 0，看能否到达矩阵边界。
// 用一个新 BFS 搜索整个连通区域：只要区域内出现边界格子就能走出去。
bool can_escape(int sx, int sy) {
    memset(vis, 0, sizeof(vis));

    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();

        // 当前格子在矩阵边界上：说明从这个 0 可以走到边界。
        if (x == 1 || x == n || y == 1 || y == n) {
            return 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] == 1) continue;
            vis[nx][ny] = true;
            q.push({nx, ny});
        }
    }
    return false;
}

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++) {
            // 每个 0 独立判断一次：走不出去就是闭合圈内部，填 2。
            if (g[i][j] == 0 && !can_escape(i, j)) {
                g[i][j] = 2;
            }
        }
    }

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

brute.cpp 对每个 0 格子都单独做一次 BFS：只走 0，看整个连通区域里是否出现矩阵边界格子，出现了就是圈外，否则就是圈内填 2。这个做法完全正确，但同一个 0 区域会被反复搜索：一个区域里有 $k$ 个 0，就可能被搜 $k$ 次，最坏 $O(n^4)$ 。虽然本题 $n \leqslant 30$ 能跑完，但思路本身有浪费——一片区域的可达性结论对所有成员相同，却要对每个成员重算一遍。

思路

关键观察是正难则反：与其从每个 0 判断"能不能走出去"，不如反过来从外面整体搜一次，把所有圈外的 0 一次找全：

圈内 0 与圈外 0 之间隔着 1，互不可达；
因此"外部搜索没访问到的 0"恰好就是"无法到达边界的 0"，也就是闭合圈内的 0。

正式主解是解法一（对应 main.cpp）：给矩阵补一圈 0 边框，外界坍缩成起点 (0,0)，从它做一次 BFS 即可覆盖全部外部区域。外部搜索也可以直接改成递归 DFS，代码见 main-dfs.cpp。解法二（对应 main2.cpp）不补边框：对每个 0 区域先用 BFS 判断它能否走到矩阵边界，不能走出去的区域再用第二次 BFS 填成 2。解法一更简洁，解法二更贴近题面定义。

解法一：补边框 + 一次外部 BFS

思路

用一个小技巧——补一圈 0 边框：把矩阵外围再包一圈 0，整个外界就变成从 (0,0) 出发的单个起点，从它做一次 BFS 就能覆盖全部外部区域，不需要枚举边界上的每个 0，也不需要任何边界特判。

用样例看外部 BFS 的效果（. 表示被外部 BFS 标记的 0，0 表示未被访问的圈内 0，1 是墙）：

text

1
2
3
4
5
6
7原方阵                      外部 BFS 标记后              最终答案
0 0 0 0 0 0                  . . . . . .                 0 0 0 0 0 0
0 0 1 1 1 1                  . . 1 1 1 1                 0 0 1 1 1 1
0 1 1 0 0 1                  . 1 1 0 0 1                 0 1 1 2 2 1
1 1 0 0 0 1                  1 1 0 0 0 1                 1 1 2 2 2 1
1 0 0 0 0 1                  1 0 0 0 0 1                 1 2 2 2 2 1
1 1 1 1 1 1                  1 1 1 1 1 1                 1 1 1 1 1 1

看中间一列：外部 BFS 从边框扩散，把闭合圈外的 0 全部标成 .，但被 1 围住的 0 一个也进不去，仍是 0。最后输出时：. -> 0，0 -> 2，1 -> 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
70
71
72
73
74/**
 * 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-08-13 13:30
 * update_at: 2026-08-13 13:31
 */
/* P1162 填涂颜色 */
/* 给矩阵补一圈 0 并从外部 BFS，未被外部搜索到的 0 就是闭合圈内部。 */

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

const int MAXN = 35;

int n;
int g[MAXN][MAXN];    // 原矩阵，下标 0..n+1，外围自动补一圈 0
int vis[MAXN][MAXN];  // vis[x][y] = 1 表示 (x,y) 是从外部可达的 0
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// 从矩阵外的一点 (0,0) 出发 BFS，把所有能走到且值为 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();

        // 四方向扩展，只走值为 0 且未访问过的格子。
        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; // 墙 1 不能通过
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
}

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

    cin >> n;
    // 读入 n*n 矩阵；全局数组初始为 0，相当于自动补了一圈 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;       // 未被访问的 0 在闭合圈内，填 2
            }
            if (j < n) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

DFS 实现

补边框后，外部区域仍然是一个连通块，因此把队列换成递归 DFS 不会改变答案。每个格子最多访问一次，最后仍然把未被外部 DFS 访问到的 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/**
 * 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-08-29 17:32
 * update_at: 2026-08-29 17:32
 */
// main-dfs.cpp：补一圈 0，从外围用 DFS 标记所有与外界连通的 0。
#include <iostream>
using namespace std;

const int MAXN = 35;

int n;
int g[MAXN][MAXN];       // 0 可以走，1 是墙
bool vis[MAXN][MAXN];    // 从外部可以到达的 0

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

// 从外围 (0,0) 出发，标记所有与外界连通的 0。
void dfs(int x, int y) {
    vis[x][y] = true;

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx < 0 || nx > n + 1 || ny < 0 || ny > n + 1)
            continue;
        if (vis[nx][ny])
            continue;
        if (g[nx][ny] == 1)
            continue;

        dfs(nx, ny);
    }
}

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

    cin >> n;

    // 全局数组默认为 0，天然补出一圈外围边框。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }

    dfs(0, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1)
                cout << " ";

            if (g[i][j] == 1)
                cout << 1;
            else if (vis[i][j])
                cout << 0;
            else
                cout << 2;
        }
        cout << "\n";
    }

    return 0;
}

复杂度

时间：BFS 或 DFS 中每个格子最多访问一次，加上一次输出扫描，总 $O(n^2)$ 。
空间：矩阵、标记数组和队列或递归栈均为 $O(n^2)$ 。

解法二：两次 BFS——先判区域能否出去，再填内部

思路

不补边框的等价写法：扫描矩阵，遇到未访问的 0 区域，先用 BFS1 判断这个区域能否走到矩阵边界：

能走出去（外部区域）：保留 0，不做任何修改；
走不出去（被包围的内部区域）：再用 BFS2 把整个区域 flood fill 成 2。

与解法一对比，两次 BFS 的做法是"对每个区域单独下结论"，本质是把题面定义"无法到达边界"直接翻译成程序；解法一的补边框法则是"一次反向搜索排除所有外部区域"。两者结论相同，解法一少一次全矩阵扫描的常数，解法二的可读性更贴近定义。两次 BFS 也可以直接改成两次 DFS，代码见 main2-dfs.cpp。

代码

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;
}

DFS 实现

解法二的两个搜索过程也可以用递归 DFS 完成：第一次 DFS 搜索整个 0 连通区域并记录它是否接触边界；如果没有接触边界，第二次 DFS 就把这个区域填成 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/**
 * 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-08-29 17:35
 * update_at: 2026-08-29 17:35
 */
// main2-dfs.cpp：第一次 DFS 判断区域是否接触边界，第二次 DFS 填涂内部区域。
#include <iostream>
using namespace std;

const int MAXN = 35;

int n;
int g[MAXN][MAXN];       // 0: 空地，1: 墙，2: 已填涂
bool vis[MAXN][MAXN];    // 第一次 DFS 的访问标记

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool can_get_out;

// 搜索一个 0 连通区域，并判断它是否能到达矩阵边界。
void dfs1(int x, int y) {
    vis[x][y] = true;

    if (x == 1 || x == n || y == 1 || y == n)
        can_get_out = true;

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx < 1 || nx > n || ny < 1 || ny > n)
            continue;
        if (vis[nx][ny])
            continue;
        if (g[nx][ny] != 0)
            continue;

        dfs1(nx, ny);
    }
}

// 把一个已经确认封闭的 0 连通区域全部填成 2。
void dfs2(int x, int y) {
    g[x][y] = 2;

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx < 1 || nx > n || ny < 1 || ny > n)
            continue;
        if (g[nx][ny] != 0)
            continue;

        dfs2(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])
                continue;

            can_get_out = false;
            dfs1(i, j);
            if (!can_get_out)
                dfs2(i, j);
        }
    }

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

    return 0;
}

复杂度

时间：每个 0 区域恰好被 BFS1/DFS1 访问一次、被 BFS2/DFS2 访问一次（仅内部区域），加上扫描与输出，总 $O(n^2)$ 。
空间：矩阵、访问标记和队列或递归栈， $O(n^2)$ 。

复杂度对比

方案	思路	边界处理	常数
解法一 main.cpp	补边框，一次外部 BFS	无需特判	更小（每个格子至多入队一次）
解法二 main2.cpp	每区域 BFS1 判定 + BFS2 填涂	需判断是否到边界	略大（内部区域会再走一次 BFS2）

两者渐近相同（ $O(n^2)$ ），选哪种取决于是否喜欢"补边框"这个技巧。

总结

"找被包围的区域"这类题的通用套路是正难则反：不逐个判断内部，而是从外部 flood fill 一次，未被访问的部分自然就是内部。补边框的写法让外界坍缩成一个起点，BFS 实现干净且不需要边界特判；不想用补边框时，对每个区域"先判定、后填涂"的两次 BFS 是等价且更贴近定义的写法。flood fill 与连通块的原理可参考 rbook 的《图的遍历》。

图示解析

这张 ASCII 图展示两种解法的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20朴素模拟（brute.cpp）
  对每个 0 单独 BFS，判断能否走到边界       最坏 O(n^4)
        |
        | 瓶颈：同一片 0 区域被反复搜索，
        |        "能否走出去"对整块连通区域是同一个结论
        v
关键观察（正难则反）
  圈内 0 与圈外 0 隔着 1，互不可达
  => 外部搜索没访问到的 0 就是闭合圈内的 0
        |
        +--------------+-------------------+
        v                                  v
解法一（main.cpp，主解）                  解法二（main2.cpp）
补一圈 0 边框，外界坍缩成 (0,0)          扫描每个 0 区域：
从 (0,0) 一次外部 BFS 标记全部圈外 0      BFS1 判能否到边界
输出：1->1，外部 0->0，圈内 0->2        不能出去则 BFS2 填成 2
        |                                  |
        +--------------+-------------------+
                       v
复杂度 O(n^2)，空间 O(n^2)

图中上方三条主线对应"暴力在哪里慢"“观察到什么性质”“正难则反的两种实现方式”。核心一步是把"每个格子独立判断"换成"整片区域共享结论"：解法一用补边框一次反向搜索，解法二用先判定后填涂，殊途同归。

目录

形式化题目

暴力

思路

解法一：补边框 + 一次外部 BFS

思路

代码

DFS 实现

复杂度

解法二：两次 BFS——先判区域能否出去，再填内部

思路

代码

DFS 实现

复杂度

复杂度对比

总结

图示解析