[蓝桥杯 2023 省 A] 像素放置

形式化题目

给定 $n \times m$ 的 $01$ 网格，其中若干格子附带一个数字 $x$ （ $0 \leqslant x \leqslant 9$ ）。数字位于 $(i,j)$ 时，要求 $(i,j)$ 及其八个相邻格（越界的格子不计数）中黑色格子的个数恰好为 $x$ 。求满足全部数字约束的 $01$ 网格。数据保证有解且解唯一。

暴力解法

思路

最直接的做法是把每个格子的颜色当成一个未知量，用一个 $01$ 序列表示整张棋盘，枚举全部 $2^{nm}$ 种染色。

按行优先的顺序递归：第 $dep$ 层决定第 $dep$ 个格子的颜色（ $dep$ 从 $0$ 开始，对应格子为 $(dep/m+1,\ dep\%m+1)$ ）。每层先试 $0$ （白）再试 $1$ （黑），递归到 $dep = nm$ 时再回头检查每个数字约束是否恰好被满足，第一个满足全部约束的方案就是字典序最小的解。

为什么必须等到最后才检查？ 因为按行优先枚举时，一个数字约束的 $3\times 3$ 窗口里总有一部分格子还没被枚举到。此时窗口内的黑格数只是一个下界，无法判断它最终是否等于 $x$ ；只有整张棋盘都确定之后，约束才变成可判定的。

这也是 brute.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/**
 * 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-03 11:16
 * update_at: 2026-10-03 11:16
 */
// brute.cpp：暴力解。按行优先顺序枚举每个格子的颜色，递归到最后一格才检查全部约束。
// 每层先试 0 再试 1，所以第一个合法方案就是字典序最小的解，和正解输出一致，方便对拍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 15;

int n, m;
int need[MAXN][MAXN];  // need[i][j] = 数字约束；-1 表示这一格没有数字
int col[MAXN][MAXN];   // 当前枚举到的染色
bool found;

// 检查整个棋盘是否满足所有数字约束
bool check_all() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (need[i][j] < 0) continue;
            int cnt = 0;
            for (int r = max(1, i - 1); r <= min(n, i + 1); r++) {
                for (int c = max(1, j - 1); c <= min(m, j + 1); c++) {
                    cnt += col[r][c];
                }
            }
            if (cnt != need[i][j]) return false;
        }
    }
    return true;
}

// dep 从 0 数到 n*m-1，对应格子 (dep/m+1, dep%m+1)
void dfs(int dep) {
    if (found) return;
    if (dep == n * m) {
        if (check_all()) found = true;
        return;
    }
    int i = dep / m + 1;
    int j = dep % m + 1;
    for (int b = 0; b <= 1; b++) {
        col[i][j] = b;
        dfs(dep + 1);
        if (found) return;
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            if (ch == '_') need[i][j] = -1;
            else need[i][j] = ch - '0';
        }
    }

    dfs(0);

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

复杂度

一共枚举 $2^{nm}$ 个完整染色，每个染色检查全部约束需要 $O(nm)$ ，总时间复杂度 $O(2^{nm} \cdot nm)$ ，空间复杂度 $O(nm)$ （棋盘数组和递归栈）。

瓶颈

瓶颈就是 $2^{nm}$ 这个枚举量： $nm=20$ 已经是 $10^6$ 级别，而题目允许 $nm = 100$ 。暴力的第二个浪费在于——它把判断推迟到了最后，前面的 $nm-1$ 层递归完全不产生任何信息，即使某个数字约束早就被填爆了，也要等整棵树走完才发现。

正解

思路

既然暴力的浪费在于“判断太晚”，就让判断尽可能早：按行优先顺序填格子，每填完一格，立刻检查那些已经能被完全确定的数字约束。

关键观察：按行优先填到 $(i,j)$ 时，哪些数字约束的窗口已经全部见过？

窗口覆盖行 $[r-1, r+1]$ 、列 $[c-1, c+1]$ ，最后被访问的格子是 $(r+1, c+1)$ 。所以数字 $(r,c)$ 在格子 $(r+1,c+1)$ 填完的瞬间被完全确定。
反过来，刚填完 $(i,j)$ 时，新被确定的约束就是 $(r,c) = (i-1, j-1)$ ——恰好一个（越界时没有）。

为了让这个检查随时可做，维护两个数组：

数组	含义
`part[r][c]`	数字 $(r,c)$ 的窗口中，已确定颜色的格子里的黑格数
`known[r][c]`	数字 $(r,c)$ 的窗口中，已确定颜色的格子数
`tot[r][c]`	数字 $(r,c)$ 的窗口落在棋盘内的格子总数（预处理，越界格不计）

填完 $(i,j)$ 后，只有与它相邻（切比雪夫距离不超过 $1$ ）的数字窗口会变化，最多 $9$ 个，逐个检查：

下界剪枝：若 part[r][c] > need[r][c]，黑格已经超标，这个约束再也不可能被满足，回溯。
上界剪枝：若 part[r][c] + (tot[r][c] - known[r][c]) < need[r][c]，即窗口内剩下未确定的格子全部填黑也不够，同样回溯。

这两条剪枝合起来，等价于对每个已确定约束做一次区间判定：part[r][c] <= need[r][c] <= part[r][c] + (tot[r][c] - known[r][c])。只要某一步破坏了这个不等式，当前分支直接死亡。

以样例的数字 $(1,2)=1$ 为例，它的窗口是第 $1\sim 2$ 行、第 $1\sim 3$ 列共 $6$ 格，最后被访问的格子是 $(2,3)$ 。当按顺序填入 $(1,1)=0$ 、 $(1,2)=0$ 、 $(1,3)=0$ 、 $(2,1)=0$ 、 $(2,2)=0$ 后，part = 0、known = 5，只剩 $(2,3)$ 一格；此时 0 <= 1 <= 0 + (6-5)，约束要求剩下的这一格必须是黑格。如果前面任何一格填了黑格，part 会立即超过 $1$ ，分支当场被剪掉。

因为数据保证解唯一，搜索找到的第一个解就是答案；即使解不唯一，由于我们始终先试 $0$ 再试 $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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * 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-03 11:16
 * update_at: 2026-10-03 11:16
 */
// main.cpp：正解。按行优先顺序逐格决定颜色(0 白 / 1 黑)，每落一子立刻检查受影响的 3x3 约束。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 15;

int n, m;
char g[MAXN][MAXN];     // 输入棋盘：数字或 '_'
int need[MAXN][MAXN];   // need[i][j] = 数字约束；-1 表示这一格没有数字
int tot[MAXN][MAXN];    // 约束 (i,j) 的窗口在棋盘内的格子总数
int part[MAXN][MAXN];   // 已确定颜色的格子中，落在窗口内的黑格数
int known[MAXN][MAXN];  // 已确定颜色的格子中，落在窗口内的格子数
int ans[MAXN][MAXN];    // 每个格子最终的颜色
bool found;             // 是否已经找到解

// 在 (i,j) 填颜色 b：s = 1 表示落子，s = -1 表示撤销
// 只会影响与 (i,j) 切比雪夫距离不超过 1 的数字约束
void apply(int i, int j, int b, int s) {
    for (int r = max(1, i - 1); r <= min(n, i + 1); r++) {
        for (int c = max(1, j - 1); c <= min(m, j + 1); c++) {
            if (need[r][c] < 0) continue;
            part[r][c] += s * b;
            known[r][c] += s;
        }
    }
}

// 判断刚落子的 (i,j) 所影响的约束是否还有可能被满足
bool feasible(int i, int j) {
    for (int r = max(1, i - 1); r <= min(n, i + 1); r++) {
        for (int c = max(1, j - 1); c <= min(m, j + 1); c++) {
            int d = need[r][c];
            if (d < 0) continue;                 // 这一格没有数字
            if (part[r][c] > d) return false;    // 黑格已经超标
            // 窗口里还没确定的格子全部填黑也不够，剪掉
            if (part[r][c] + tot[r][c] - known[r][c] < d) return false;
        }
    }
    return true;
}

void dfs(int i, int j) {
    if (found) return;
    if (i > n) {         // 所有格子都已确定，过程中每个约束都被检查过
        found = true;
        return;
    }
    int ni = i, nj = j + 1;
    if (nj > m) { ni = i + 1; nj = 1; }
    for (int b = 0; b <= 1; b++) {   // 先试白色，保证得到的是字典序最小的解
        ans[i][j] = b;
        apply(i, j, b, 1);
        if (feasible(i, j)) dfs(ni, nj);
        apply(i, j, b, -1);
        if (found) return;
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == '_') need[i][j] = -1;
            else need[i][j] = g[i][j] - '0';
        }
    }

    // 预处理每个约束窗口落在棋盘内的格子个数，棋盘外的格子不参与计数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int r1 = max(1, i - 1), r2 = min(n, i + 1);
            int c1 = max(1, j - 1), c2 = min(m, j + 1);
            tot[i][j] = (r2 - r1 + 1) * (c2 - c1 + 1);
        }
    }

    dfs(1, 1);

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

复杂度

每个格子只有 $0/1$ 两种取值，搜索树规模上界仍是 $O(2^{nm})$ ，但每落一子只做常数次（ $\leqslant 9$ 个窗口）的剪枝判断，单步代价 $O(1)$ ；预处理 $tot$ 需要 $O(nm)$ 。空间复杂度 $O(nm)$ （need、part、known、tot、ans 各为 $n \times m$ ）。在 $n,m \leqslant 10$ 且解唯一的数据上，剪枝会把搜索树压到实际可接受的规模。

总结

暴力的问题在于判断太晚：按行优先枚举时，只有整张棋盘填完才能检查约束，前面所有递归都不产生剪枝信息。
正解的改进是让约束“何时可判定”变得精确：数字 $(r,c)$ 的窗口在格子 $(r+1,c+1)$ 填完时被完全确定，所以每落一子只需检查最多 $9$ 个窗口。
剪枝的本质是区间判定：维护窗口内「已确定黑格数 part」和「已确定格子数 known」，一旦 part > need 或 part + (tot - known) < need 就回溯。
这类「枚举 + 提前检查局部约束」的搜索题，通法是先想清楚每做出一个决策后，哪些约束的取值区间会被更新，再把约束的可行区间作为剪枝条件；本题的约束只有 $3\times 3$ 一小块，因此每次决策的影响面是常数级，剪枝既便宜又有效。