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

封面图：https://t.bilibili.com/961668217500073990

题目描述

小蓝最近迷上了一款名为《像素放置》的游戏，游戏在一个 $n \times m$ 的网格棋盘上进行，棋盘含有 $n$ 行，每行包含 $m$ 个方格。玩家的任务就是需要对这 $n \times m$ 个方格进行像素填充，填充颜色只有黑色或白色两种。有些方格中会出现一个整数数字 $x(0 \leq x \leq 9)$，这表示当前方格加上周围八个方向上相邻的方格（分别是上方、下方、左方、右方、左上方、右上方、左下方、右下方）共九个方格内有且仅有 $x$ 个方格需要用黑色填充。

玩家需要在满足所有数字约束下对网格进行像素填充，请你帮助小蓝来完成。题目保证所有数据都有解并且解是唯一的。

输入格式

输入的第一行包含两个整数 $n,m$，用一个空格分隔，表示棋盘大小。

接下来 $n$ 行，每行包含 $m$ 个字符，表示棋盘布局。字符可能是数字 $0 \sim 9$，这表示网格上的数字；字符还有可能是下划线（$\text{ASCII}$ 码为 $95$），表示一个不带有数字的普通网格。

输出格式

输出 $n$ 行，每行包含 $m$ 个字符，表示答案。如果网格填充白色则用字符 $0$ 表示，如果网格填充黑色则用字符 $1$ 表示。

样例 #1

样例输入 #1

1
2
3
4
5
6
7


6 8
_1__5_1_
1_4__42_
3__6__5_
___56___
_688___4
_____6__

样例输出 #1

提示

【样例说明】

上图左是样例数据对应的棋盘布局，上图右是此局游戏的解。例如第 $3$ 行第 $1$ 列处的方格中有一个数字 $3$，它周围有且仅有 $3$ 个格子被黑色填充，分别是第 $3$ 行第 $2$ 列、第 $4$ 行第 $1$ 列和第 $4$ 行第 $2$ 列的方格。

【评测用例规模与约定】

对于 $50 %$ 的评测用例，$1 \leq n,m \leq 5$；

对于所有评测用例，$1 \leq n,m \leq 10$。

解题思路

很简单的深度优先搜索……仅就官方数据而言。实际上深搜的时间复杂度是很危险的，不过官方数据比较水，深搜能全过，洛谷上就会被卡掉几个点。不过也可能是被卡常了。但这道题用搜索性价比还是很高的，写起来比较快也能拿大多数分。

具体做法就是每个点去深搜，从左到右从上到下，每当一个数字周围的点都已经填了 $0$ 或 $1$ 时就检查这个数字是否合法，不合法就直接剪枝。

这么水的解法之所以要写题解，主要是记录一下这张图的存储方法。如果按一般的方法用矩阵存储这张图，那么在判断“一个数字周围的点都已经填了 $0$ 或 $1$”这一步时就会很不优雅。因为在深搜的过程中，并不是按数字周边去深搜的，而是按顺序；因此这一步从判断数字周围的情况，变为了判断当前填入的这个点是否是“某个数字周围最后的点”。很容易想到一个数字周围最后的点应该是它右下角的点，如果它右下角的点已经被填了，那么它周围的所有点应该都被填了。但是这并非绝对，要处理三种特殊情况，即数字在图的最右侧、数字在图的最下方、数字在图的右下角。我在第一次写时就遗漏了最后一种特殊情况，导致只通过了一个点。还有一个陷阱是可能有多个数字会同时需要检查。

要解决这个问题，有两个技巧：

将图建大一圈，避免数组访问越界的问题。注意到统计一个数字周围时，只需要统计周围 $1$ 的个数即可，所以可以在图的周围填一圈 $0$，这样无论边缘还是中心的数字都可以统计周围一圈，不用担心越界问题。
在存储图时，不存储数字，而是存储“检查点”。“检查点”就是上文中提到的“一个数字周围最后的点”。当 DFS 填到“检查点”时，就意味着要触发“检查”。一个数字对应的“检查点”其实就是其右下角的座标和边界取最小值，这样就把复杂的 $8$ 个判断条件简化为 $2$ 个 min 语句，而且在输入时处理即可，搜索算法内部实现可以做到非常简洁。注意到一个座标可能是多个数字的检查点，因此对于每个座标使用一个链表来存储所有检查点，即使用一个链表类型的二维数组来存储这张图。

使用这两个技巧之后，在搜索算法内部不需要添加任何的额外判断，所有数字的处理方法都是一致的。在输入时仅需要加入一行语句来处理边缘点即可。非常优雅。

代码

附上实现代码（该代码蓝桥杯官网全过，洛谷只能92分）：

 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


#include <algorithm>
#include <iostream>
#include <list>
using namespace std;
struct loc
{
    int x, y;
};
struct point
{
    loc l;
    int v;
};
const int MAXN = 15;
const loc NEAR[9] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 0}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int result[MAXN][MAXN];
int n, m;
list<point> g[MAXN][MAXN];

void printresult()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << result[i][j];
        }
        cout << endl;
    }
}
loc add(loc a)
{
    if (a.y == m)
    {
        a.x++;
        a.y = 1;
        return a;
    }
    else
    {
        a.y++;
        return a;
    }
}
bool check(const loc &cur)
{
    for (auto i : g[cur.x][cur.y])
    {
        int &x = i.l.x, &y = i.l.y;
        int sum=0;
        for (auto j:NEAR)
        {
            sum+=result[x+j.x][y+j.y];
        }
        if (sum!=i.v) return false;
    }
    return true;
}
bool dfs(loc cur)
{
    if (cur.x > n || cur.y > m)
    {
        return true;
    }
    result[cur.x][cur.y] = 1;
    if (check(cur))
        if (dfs(add(cur)))
            return true;
    result[cur.x][cur.y] = 0;
    if (check(cur))
        if (dfs(add(cur)))
            return true;
    return false;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            do
            {
                c = getchar();
            } while (c != 95 && (c < '0' || c > '9'));
            if (c >= '0' && c <= '9')
            {
                int x = min(i + 1, n), y = min(j + 1, m);
                g[x][y].push_back({{i, j}, c - '0'});
            }
        }
    }
    dfs({1, 1});
    printresult();
    return 0;
}