Stamp Grid

题意

给定一个 $N \times N$ 的目标图案， $*$ 表示黑格，. 表示白格。

还有一个 $K \times K$ 的印章。每次可以把印章旋转 $0^\circ,90^\circ,180^\circ,270^\circ$ 后，放在画布内某个位置盖一次。

印章上的 $*$ 会把对应位置涂黑；已经涂黑的格子不会变回白色。

问能否从全白画布出发，盖出目标图案。

思路

先看一个直接模拟所有合法盖章位置的朴素写法：

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/**
 * 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-11 16:44
 * update_at: 2026-07-11 16:46
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int test_count;
int n, k;
char target_grid[MAXN][MAXN];
char stamp_grid[4][MAXN][MAXN];
char painted[MAXN][MAXN];

void build_rotations() {
    for (int rot = 1; rot < 4; rot++) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                stamp_grid[rot][i][j] = stamp_grid[rot - 1][k - 1 - j][i];
            }
        }
    }
}

bool can_stamp(int rot, int x, int y) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (stamp_grid[rot][i][j] == '*' && target_grid[x + i][y + j] == '.') {
                return false;
            }
        }
    }
    return true;
}

void do_stamp(int rot, int x, int y) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (stamp_grid[rot][i][j] == '*') {
                painted[x + i][y + j] = '*';
            }
        }
    }
}

bool solve_one() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < n; j++) {
            target_grid[i][j] = row[j];
            painted[i][j] = '.';
        }
    }

    cin >> k;
    for (int i = 0; i < k; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < k; j++) {
            stamp_grid[0][i][j] = row[j];
        }
    }

    build_rotations();

    // 小数据朴素做法：枚举所有旋转和所有位置，只要不会盖到白格就盖。
    for (int rot = 0; rot < 4; rot++) {
        for (int i = 0; i + k <= n; i++) {
            for (int j = 0; j + k <= n; j++) {
                if (can_stamp(rot, i, j)) {
                    do_stamp(rot, i, j);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (painted[i][j] != target_grid[i][j]) {
                return false;
            }
        }
    }
    return true;
}

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

    cin >> test_count;
    while (test_count--) {
        cout << (solve_one() ? "YES" : "NO") << '\n';
    }

    return 0;
}

本题有一个很重要的单调性：盖章只会把格子变黑，不会把黑格变白。

所以如果某次盖章会覆盖到目标图案中的白格 .，这次盖章一定不能出现在任何合法方案中。

反过来，如果某次盖章只会覆盖目标图案中的黑格 $*$ ，那么把它盖上不会破坏答案。即使原来的某个方案没有使用它，多盖这一次也只是让一些目标黑格变黑，不会产生多余黑格。

因此可以采取最贪心的做法：

枚举印章的四种旋转。
枚举印章左上角位置。
如果这次盖章不会盖到目标白格，就把它盖到 painted 上。
最后比较 painted 是否和目标图案完全相同。

旋转公式可以写成：

text

1rotated[i][j] = old[k - 1 - j][i]

这样每次得到顺时针旋转 $90^\circ$ 后的印章。

如果最后还有某个目标黑格没有被覆盖，说明无论怎么选合法盖章位置都无法得到它，答案就是 NO。

代码

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/**
 * 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-11 16:44
 * update_at: 2026-07-11 16:46
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int test_count;
int n, k;
char target_grid[MAXN][MAXN];
char stamp_grid[4][MAXN][MAXN];
char painted[MAXN][MAXN];

void build_rotations() {
    for (int rot = 1; rot < 4; rot++) {
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                stamp_grid[rot][i][j] = stamp_grid[rot - 1][k - 1 - j][i];
            }
        }
    }
}

bool can_stamp(int rot, int x, int y) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (stamp_grid[rot][i][j] == '*' && target_grid[x + i][y + j] == '.') {
                return false;
            }
        }
    }
    return true;
}

void do_stamp(int rot, int x, int y) {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (stamp_grid[rot][i][j] == '*') {
                painted[x + i][y + j] = '*';
            }
        }
    }
}

bool solve_one() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < n; j++) {
            target_grid[i][j] = row[j];
            painted[i][j] = '.';
        }
    }

    cin >> k;
    for (int i = 0; i < k; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < k; j++) {
            stamp_grid[0][i][j] = row[j];
        }
    }

    build_rotations();

    for (int rot = 0; rot < 4; rot++) {
        for (int i = 0; i + k <= n; i++) {
            for (int j = 0; j + k <= n; j++) {
                if (can_stamp(rot, i, j)) {
                    do_stamp(rot, i, j);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (painted[i][j] != target_grid[i][j]) {
                return false;
            }
        }
    }
    return true;
}

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

    cin >> test_count;
    while (test_count--) {
        cout << (solve_one() ? "YES" : "NO") << '\n';
    }

    return 0;
}

复杂度

共有 $4$ 种旋转，最多 $(N-K+1)^2$ 个位置，每次检查和盖章需要 $O(K^2)$ 。

时间复杂度为 $O(4N^2K^2)$ ，在 $N \leqslant 20$ 下足够。

空间复杂度为 $O(N^2+K^2)$ 。

总结

这题的关键不是搜索盖章顺序，而是利用“只能变黑”的单调性。

所有不会污染白格的盖章都可以放心使用，最后只需要检查是否覆盖了所有目标黑格。

目录

题意

思路

代码

复杂度

总结