Astral Superposition

GitHub 跳转原题关系图返回列表

先强制满足黑色像素，再检查白色冲突，并用贪心为未满足的灰色像素补星星。

OJ: usaco

题目 ID: 1467

难度:普及-

标签:贪心模拟

日期: 2026-07-11 12:25

题意

有一张星空照片，初始时某些格子有星星。

一夜之后，每颗星星要么消失，要么向右移动 $A$ 、向下移动 $B$ 。如果移出照片范围，就不会出现在第二张照片中。

现在把第一张照片和第二张照片叠加，得到一张颜色图：

W：两张照片这个位置都没有星星；
G：两张照片恰好一张有星星；
B：两张照片这个位置都有星星。

要求判断这张叠加图是否可能出现。如果可能，求初始照片中星星数量的最小值。

思路

暴力想法

最直接的想法是枚举初始照片中每个格子有没有星星。

枚举出一张初始照片后，再逐格判断它能否通过“消失或移动”解释最终颜色。

下面的暴力把每个格子看成一个 01 选择：choose_star[i]=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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130/**
 * 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 12:25
 * update_at: 2026-07-11 12:27
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 6;
const int MAXC = 30;

int n, a, b;
int total_cell;
char color[MAXN][MAXN];
int choose_star[MAXC]; // choose_star[k]=1 表示第 k 个格子在初始照片中有星星
bool first_photo[MAXN][MAXN];
int best;

void cell_pos(int id, int &r, int &c) {
    r = (id - 1) / n + 1;
    c = (id - 1) % n + 1;
}

bool has_source(int r, int c) {
    return r - b >= 1 && c - a >= 1;
}

bool check_choice() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            first_photo[i][j] = false;
        }
    }

    for (int id = 1; id <= total_cell; id++) {
        int r, c;
        cell_pos(id, r, c);
        if (choose_star[id] == 1) {
            first_photo[r][c] = true;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            bool first = first_photo[i][j];
            bool need_second = false;

            if (color[i][j] == 'W') {
                if (first) {
                    return false;
                }
                need_second = false;
            } else if (color[i][j] == 'G') {
                // 灰色表示前后两张照片恰好一张有星星。
                need_second = !first;
            } else {
                if (!first) {
                    return false;
                }
                need_second = true;
            }

            if (need_second) {
                if (!has_source(i, j)) {
                    return false;
                }
                if (!first_photo[i - b][j - a]) {
                    return false;
                }
            }
        }
    }

    return true;
}

void dfs_choose(int dep, int cnt) {
    if (cnt >= best) {
        return;
    }
    if (dep == total_cell + 1) {
        if (check_choice()) {
            best = cnt;
        }
        return;
    }

    // 这一层选择当前格子初始时有没有星星。
    choose_star[dep] = 0;
    dfs_choose(dep + 1, cnt);

    choose_star[dep] = 1;
    dfs_choose(dep + 1, cnt + 1);
}

int solve_one() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            color[i][j] = s[j - 1];
        }
    }

    total_cell = n * n;
    best = total_cell + 1;
    dfs_choose(1, 0);

    if (best == total_cell + 1) {
        return -1;
    }
    return best;
}

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

    int t;
    cin >> t;
    while (t--) {
        cout << solve_one() << '\n';
    }

    return 0;
}

暴力的瓶颈是初始照片有 $N^2$ 个格子，需要枚举 $2^{N^2}$ 种星星集合。

两遍扫描

对于位置 (r,c)，第二张照片中出现在这里的星星，只能来自：

text

1(r-B, c-A)

如果这个来源位置越界，就不可能有星星移动到 (r,c)。

先看黑色像素 B。它表示两张照片在当前位置都有星星，所以：

text

1
2has_star[r][c] = true
has_star[r-B][c-A] = true

如果来源越界，直接无解。

处理完所有黑色像素后，再扫描白色和灰色：

W：当前位置不能有初始星星，如果 has_star[r][c] 已经为真，则无解；
G：如果当前位置已有初始星星，可以让它消失，当前像素就是灰色；
G：否则如果来源位置已有初始星星，可以让它移动过来，当前像素也是灰色；
G：如果两者都没有，就必须新增一颗星星。把它放在当前位置最优，因为它还能作为后续位置的来源。

这个贪心依赖扫描顺序：按行从上到下、每行从左到右扫描时，(r-B,c-A) 一定不会晚于 (r,c)，所以来源位置是否有星星已经确定。

最后统计 has_star 中的星星数量。

灰色格子的贪心本质

这题真正容易想错的地方在灰色格子。

灰色 G 的意思是：当前位置和来源位置中，恰好有一个能解释这个像素。把它写成逻辑关系，就是：

has\_star(r,c) \oplus has\_star(r-B,c-A)

从人脑思考的角度，可以把每个灰色格子看成一个需求：

text

1当前位置有星星，或者来源位置有星星，至少要满足一个。

为了让初始星星数量最少，能不新增就不新增：

如果当前位置已经有星星，这个灰色格子已经满足；
否则如果来源位置已经有星星，也可以借来源星星移动过来；
如果两边都没有，就必须新增一颗星星。

关键是最后一种情况：为什么新增时放在当前位置，而不是放在来源位置？

因为扫描到 (r,c) 时，来源位置 (r-B,c-A) 已经在扫描顺序中过去了。现在再把星星补到来源位置，只会影响已经处理过的格子，可能制造新的冲突；而放在当前位置，不仅能满足当前灰色格子，还可能作为后面格子的来源。

所以灰色格子的贪心可以记成一句话：

text

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
99
100
101
102
103/**
 * 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 12:25
 * update_at: 2026-07-11 12:27
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, a, b;
char color[MAXN][MAXN];
bool has_star[MAXN][MAXN]; // has_star[i][j] 表示初始照片中这个位置有星星

void clear_case() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            has_star[i][j] = false;
        }
    }
}

bool has_source(int r, int c) {
    return r - b >= 1 && c - a >= 1;
}

int solve_one() {
    cin >> n >> a >> b;
    clear_case();

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            color[i][j] = s[j - 1];
        }
    }

    bool ok = true;

    // 黑色像素表示前后两张照片这里都有星星。
    // 因此当前位置必须有初始星星，且它的来源位置也必须有初始星星并移动过来。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (color[i][j] == 'B') {
                has_star[i][j] = true;
                if (!has_source(i, j)) {
                    ok = false;
                } else {
                    has_star[i - b][j - a] = true;
                }
            }
        }
    }

    if (!ok) {
        return -1;
    }

    // 白色不能有初始星星；灰色必须恰好由当前位置或来源位置贡献一颗星星。
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (color[i][j] == 'W') {
                if (has_star[i][j]) {
                    return -1;
                }
            } else if (color[i][j] == 'G') {
                if (has_star[i][j]) {
                    continue;
                }
                if (has_source(i, j) && has_star[i - b][j - a]) {
                    continue;
                }
                has_star[i][j] = true;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (has_star[i][j]) {
                ans++;
            }
        }
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        cout << solve_one() << '\n';
    }

    return 0;
}

复杂度

每组数据只扫描常数遍网格，时间复杂度 $O(N^2)$ 。

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

由于题目保证所有测试用例的 $N^2$ 之和不超过 $10^7$ ，这个复杂度可以通过。

总结

这题的关键是把叠加颜色拆成“第一张照片是否有星星”和“第二张照片是否有星星”。

黑色像素给出强制条件，白色像素负责发现冲突，灰色像素再用贪心补齐。固定偏移让每个位置只有唯一来源，所以两遍扫描就能完成构造和判定。

1467 Astral Superposition

赛事信息

USACO 2025 January Contest, Bronze

题目描述

注意：本题的时间限制为 4 秒，通常限制的 2 倍。 Bessie 正在使用她超酷的望远镜拍摄夜空中所有星星的照片。她的望远镜能够拍摄到一张 $N \times N$ （ $1 \leq N \leq 1000$ ）的星星照片，其中每个像素是一颗星星或者空旷的天空。每颗星星可由恰好一个像素表示，并且没有两颗不同的星星位于同一像素内。一夜之间，一些奇怪的事情发生在了天空中的星星之上。每颗星星要么消失，要么向右移动 $A$ 像素，并且向下移动 $B$ 像素（ $0 \leq A,B \leq N$ ）。如果一颗星星消失或移动超出照片边界，它将不再出现在第二张照片中。 Bessie 在星星移动位置之前和之后拍了照片，但在 Mootoshop 中进行了一些实验后，她不小心将一张照片叠加到了另一张上。现在，她可以在两张照片都是天空的位置看到白色（white）像素，在星星仅存在于恰好一张照片的位置看到灰色（gray）像素，而在两张照片中都有星星的位置看到黑色（black）像素。Bessie 同时记得没有新的星星移动入第二张照片的范围，从而她的第一张照片包含了夜空中所有的星星。对于 $T$ （ $1 \leq T \leq 1000$ ）个独立的测试用例，给定最终的照片，求在移动事件发生之前天空中星星的最小可能数量。如果不存在星星的排列可以产生给定的最终照片，输出 $-1$ 。

输入格式

输入的第一行包含 $T$ ，以下为 $T$ 个测试用例。每个测试用例的第一行包含 $N$ $A$ $B$ 。以下 $N$ 行，每行表示叠加后的照片的一行。从上到下第 $i$ 行由一个字符串 $c_{i,1}c_{i,2}\dots c_{i,N}$ 表示，其中 $c_{i,j} \in \{W,G,B\}$ ，分别表示颜色为白色，灰色以及黑色。输入保证所有测试用例的 $N^2$ 之和不超过 $10^7$ 。

输出格式

对于每一个测试用例，输出移动之前存在的星星的最小数量，或 $-1$ 表示不可能。

输入输出样例 #1

输入 #1

text

1
2
3
4
51
3 0 0
WWB
BBB
GGG

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
153
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWW

输出 #2

text

样例说明

在第一个测试用例中，初始时至少有 $4$ 颗星星。如果我们令 $(r,c)$ 表示从上到下第 $r$ 行和从左到右第 $c$ 列的交点，一种可能性是它们最初位于 $(1,1)$ ， $(3,2)$ ， $(2,2)$ 和 $(1,3)$ 。除了位于 $(2,2)$ 的星星消失之外，其他所有星星都移动了。在第二个测试用例中，在给定的移动方式下，没有任何初始照片中的星星排列可以产生中间的黑色像素。在第三个测试用例中，初始时至少有 $4$ 颗星星。一种可能性是它们最初位于 $(1,1)$ ， $(1,2)$ ， $(1,3)$ 和 $(2,1)$ 。在第二张照片中，原先位于 $(1,1)$ 的星星消失了，原先位于 $(1,3)$ 的星星移出了照片边界。其他两颗星星向右移动了 $1$ 像素。

测试点性质

测试点 3： $A=B=0$ 。
测试点 4-7： $A=1$ ， $B=0$ ， $N\le 10$ 。
测试点 8-9： $A=1$ ， $B=0$ 。
测试点 10-12：没有额外限制。

Astral Superposition

目录

题意

思路

暴力想法

两遍扫描

灰色格子的贪心本质

代码

复杂度

总结