夜空繁星

形式化题目

给定 $H \times W$ 的 0/1 字符矩阵，1 表示星星。

星座：由水平、垂直或对角相邻（即 8 连通）的星星组成的极大连通块。
相似：两个星座经过任意次旋转（ $90^\circ$ 、 $180^\circ$ 、 $270^\circ$ ）或翻转（共 8 种等距变换）后形状完全一致。相似的两个星座星星数必然相同。

任务：按从上到下、从左到右的扫描顺序，给互不相似的星座依次分配小写字母 a、b、c、……（不相似的星座不超过 26 种），相似的星座共用同一个字母；把星座中每颗星的 1 替换成对应字母后输出整个矩阵。

数据范围： $0 \leqslant W, H \leqslant 100$ ，星座数 $\leqslant 500$ ，每个星座 $1 \sim 160$ 颗星。

正解

思路

第一步：提取星座。 天体图里的每个 8 连通块就是一个星座。从左上角扫描网格，遇到还没被访问过的 1 就从它出发做一次洪填（DFS/BFS，八方向扩展），得到一个连通块的所有格子。扫描时第一个碰到的格子一定落在「尚未标号的最左上角的星座」里，所以按这个顺序处理星座，分配字母的顺序天然就是题面要求的顺序。

第二步：把「相似」变成「指纹相等」。 朴素的判同方法是：对每对新星座，枚举其中一方的 8 种变换，再逐格比对（还要平移对齐）——星座最多 500 个，两两比较再加 8 变换逐格比对，最坏大约 $500^2 \times 8 \times 160$ 次 cell 级操作，太慢也不必要。

更好的办法是给每个形状算一个规范指纹：

对形状的 8 种 D4 变换（恒等、旋转 $90^\circ/180^\circ/270^\circ$ 、三种镜像），分别把变换后的点集平移到最小行、最小列为 0（消除位置差异）；
把点集转成排好序的坐标序列，8 个形态里取字典序最小的那个作为指纹。

两个星座相似 ⟺ 它们的指纹相同。于是「判同」退化成一次 dict 查找：

text

1
2marks: 指纹 -> 字母
mark = marks.setdefault(指纹, 下一个未用过的字母)

setdefault 一行同时完成「查重」和「分配」：第一次见到的指纹领走新字母，之后所有相似星座查到同一个字母。

第三步：回写网格。 把连通块里的每个格子对应的字符从 1 改成字母，最后整图输出。

下面的样例局部展示了指纹的思想——同一个三连块无论怎么放，8 种平移归一化形态里最小的那个都一样：

摆放方向	连通块内的格子（行, 列）	平移归一化后	规范指纹
竖放	(0,0) (1,0) (2,0)	不动	(0,0) (1,0) (2,0)
横放	(0,0) (0,1) (0,2)	旋转 $90^\circ$ 后归一化	(0,0) (1,0) (2,0)
反横放	(0,2) (0,3) (0,4)	旋转 $90^\circ$ 、平移	(0,0) (1,0) (2,0)

三种摆法算出的指纹完全一致，因此共享同一个字母；而一个 L 形三连块的指纹集合不同，会领走下一个字母。

整个流程如下：

flowchart LR
    A[读入天体图] --> B[收集所有为 1 的格子]
    B --> C[取剩余最小坐标格子做种子]
    C --> D[八方向洪填得到一个连通块]
    D --> E[对 8 种 D4 变换做平移归一化<br/>取字典序最小作为指纹]
    E --> F{指纹见过吗?}
    F -- 否 --> G[分配下一个字母 a..z]
    F -- 是 --> H[复用已有字母]
    G --> I[把块内 1 替换成字母]
    H --> I
    I --> J{还有剩余格子?}
    J -- 是 --> C
    J -- 否 --> K[输出标号后的天体图]

代码

Python 版：

python

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#!/usr/bin/env python3
# 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-01 07:09
# update_at: 2026-10-01 07:09

import sys

# 8 种等距变换（D4 群）：原样、上下翻、左右翻、旋转 180°、旋转 90°/270° 及其组合
D4 = (
    lambda r, c: (r, c),
    lambda r, c: (-r, c),
    lambda r, c: (r, -c),
    lambda r, c: (-r, -c),
    lambda r, c: (c, -r),
    lambda r, c: (-c, -r),
    lambda r, c: (c, r),
    lambda r, c: (-c, r),
)


def canonical(shape: frozenset[tuple[int, int]]) -> tuple[tuple[int, int], ...]:
    """形状的规范指纹：8 种变换各自平移到最小行列后，取字典序最小的形态。"""

    def at_origin(pts: frozenset[tuple[int, int]]) -> tuple[tuple[int, int], ...]:
        r0 = min(r for r, _ in pts)
        c0 = min(c for _, c in pts)
        return tuple(sorted((r - r0, c - c0) for r, c in pts))

    # 注意不能用 min 比较 frozenset：< 对集合是子集判断而非全序，同构形状会选出不同代表
    return min(at_origin(frozenset(f(r, c) for r, c in shape)) for f in D4)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    width = int(next(data))  # 列数
    depth = int(next(data))  # 行数
    grid = [next(data).decode() for _ in range(depth)]
    cells = {(r, c) for r, row in enumerate(grid) for c, ch in enumerate(row) if ch == '1'}

    marks: dict[tuple, str] = {}  # 形状指纹 -> 已分配的小写字母
    while cells:
        # 网格里坐标最小的剩余星星必是它所在星座的最左上角，从它出发洪填整个连通块
        start = min(cells)
        comp: set[tuple[int, int]] = {start}
        frontier = [start]
        while frontier:
            r, c = frontier.pop()
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    p = (r + dr, c + dc)
                    if p in cells and p not in comp:
                        comp.add(p)
                        frontier.append(p)
        cells -= comp

        key = canonical(frozenset(comp))
        mark = marks.setdefault(key, chr(ord('a') + len(marks)))
        for r, c in comp:
            grid[r] = grid[r][:c] + mark + grid[r][c + 1:]

    print('\n'.join(grid))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169/**
 * 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-06 11:40
 * update_at: 2026-10-06 11:40
 */

// 星空题：星座 = 8 连通块；相似 = 经过 8 种 D4 变换后形状一致。
// 做法：洪填提取每个星座 -> 算规范指纹（8 种变换各自平移归一化后取字典序最小的点集）
// -> 指纹第一次出现领新字母，之后相似的星座复用同一个字母。

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

typedef long long ll;

const int MAXN = 105;  // 天体图最大宽度和深度
const int MAXP = 165;  // 每个星座最多 160 颗星
const int MAXC = 505;  // 星座最多 500 个

int W, H;
char grid[MAXN][MAXN]; // 天体图，grid[行][列]，'1' 表示星星，最后被替换成字母
bool vis[MAXN][MAXN];  // 洪填时标记格子是否已经属于处理过的星座

ll star_r[MAXP], star_c[MAXP]; // 洪填收集到的当前星座的原始格子坐标
ll star_cnt;                   // 当前星座的星星数

ll norm_r[8][MAXP], norm_c[8][MAXP]; // 第 k 种 D4 变换平移归一化后的点集

pair<ll, ll> best_shape[MAXP]; // 当前星座的规范指纹：8 种形态里字典序最小的点集

// 已见指纹表：finger[i] = 第 i 个「新字母星座」的规范指纹
pair<ll, ll> finger[MAXC][MAXP];
ll finger_len[MAXC];
ll finger_cnt; // 已存指纹个数 = 已分配字母个数

// 检查 (r, c) 是否在天体图内。
bool in_map(ll r, ll c) {
    return r >= 0 && r < H && c >= 0 && c < W;
}

// 八方向 BFS 洪填：从 (sr, sc) 出发收集整个 8 连通块的原始坐标。
void flood_fill(ll sr, ll sc) {
    star_cnt = 0;
    ll qr[MAXN * MAXN], qc[MAXN * MAXN]; // BFS 队列（行、列）
    ll head = 0, tail = 0;
    qr[tail] = sr; qc[tail] = sc; tail++;
    vis[sr][sc] = true;

    while (head < tail) {
        ll r = qr[head], c = qc[head];
        head++;
        star_r[star_cnt] = r; star_c[star_cnt] = c; star_cnt++;
        for (ll dr = -1; dr <= 1; dr++) {
            for (ll dc = -1; dc <= 1; dc++) {
                if (dr == 0 && dc == 0) continue;
                ll nr = r + dr, nc = c + dc;
                if (!in_map(nr, nc)) continue;
                if (grid[nr][nc] != '1' || vis[nr][nc]) continue;
                vis[nr][nc] = true;
                qr[tail] = nr; qc[tail] = nc; tail++;
            }
        }
    }
}

// 生成第 k 种 D4 变换的平移归一化点集，存进 norm_r[k]/norm_c[k]。
// 8 种变换：(r,c) (r,-c) (-r,c) (-r,-c) (c,r) (c,-r) (-c,r) (-c,-r)。
void make_transform(ll k) {
    ll min_r = LLONG_MAX, min_c = LLONG_MAX;
    for (ll i = 0; i < star_cnt; i++) {
        ll r, c;
        if (k == 0)      { r = star_r[i];  c = star_c[i];  }
        else if (k == 1) { r = star_r[i];  c = -star_c[i]; }
        else if (k == 2) { r = -star_r[i]; c = star_c[i];  }
        else if (k == 3) { r = -star_r[i]; c = -star_c[i]; }
        else if (k == 4) { r = star_c[i];  c = star_r[i];  }
        else if (k == 5) { r = star_c[i];  c = -star_r[i]; }
        else if (k == 6) { r = -star_c[i]; c = star_r[i];  }
        else             { r = -star_c[i]; c = -star_r[i]; }
        norm_r[k][i] = r; norm_c[k][i] = c;
        if (r < min_r) min_r = r;
        if (c < min_c) min_c = c;
    }
    // 平移到最小行、最小列为 0，消除星座在天体图中的位置差异
    for (ll i = 0; i < star_cnt; i++) {
        norm_r[k][i] -= min_r;
        norm_c[k][i] -= min_c;
    }
}

// 计算当前星座的规范指纹：8 种形态各自排序后取字典序最小，结果存进 best_shape。
void compute_canonical() {
    for (ll i = 0; i < star_cnt; i++) {
        best_shape[i] = make_pair(norm_r[0][i], norm_c[0][i]);
    }
    sort(best_shape, best_shape + star_cnt);

    for (ll k = 1; k < 8; k++) {
        pair<ll, ll> cur[MAXP]; // 第 k 种变换排序后的点集
        for (ll i = 0; i < star_cnt; i++) {
            cur[i] = make_pair(norm_r[k][i], norm_c[k][i]);
        }
        sort(cur, cur + star_cnt);

        // 逐点比较，谁字典序小谁当新的规范形态
        for (ll i = 0; i < star_cnt; i++) {
            if (cur[i] == best_shape[i]) continue;
            if (cur[i] < best_shape[i]) {
                for (ll j = 0; j < star_cnt; j++) best_shape[j] = cur[j];
            }
            break;
        }
    }
}

int main() {
    scanf("%d %d", &W, &H);
    for (ll i = 0; i < H; i++) {
        scanf("%s", grid[i]);
    }

    for (ll i = 0; i < H; i++) {
        for (ll j = 0; j < W; j++) {
            if (grid[i][j] != '1' || vis[i][j]) continue;
            // 按扫描顺序遇到的连通块就是尚未标号的最左上角星座，字母按顺序分配
            flood_fill(i, j);

            // 先用原始坐标把字母写进图（后续变换只读副本，不动 star_r/star_c）
            for (ll t = 0; t < star_cnt; t++) {
                grid[star_r[t]][star_c[t]] = 'a' + finger_cnt;
            }

            // 生成 8 种平移归一化形态，算规范指纹
            for (ll k = 0; k < 8; k++) make_transform(k);
            compute_canonical();

            // 指纹查重：和之前所有「领过新字母」的星座逐一比较
            bool found = false;
            for (ll id = 0; id < finger_cnt; id++) {
                if (finger_len[id] != star_cnt) continue;
                bool same = true;
                for (ll t = 0; t < star_cnt; t++) {
                    if (finger[id][t] != best_shape[t]) { same = false; break; }
                }
                if (same) {
                    found = true;
                    // 相似星座复用第 id 个字母，把刚才写的字母改回去
                    for (ll t = 0; t < star_cnt; t++) {
                        grid[star_r[t]][star_c[t]] = 'a' + id;
                    }
                    break;
                }
            }
            if (!found) {
                // 新形状：保存指纹，字母保持 'a'+finger_cnt 不变
                finger_len[finger_cnt] = star_cnt;
                for (ll t = 0; t < star_cnt; t++) finger[finger_cnt][t] = best_shape[t];
                finger_cnt++;
            }
        }
    }

    for (ll i = 0; i < H; i++) {
        printf("%s\n", grid[i]);
    }
    return 0;
}

实现里有一个值得单独指出的细节：规范化时不能把 8 个形态保留成 frozenset 再用 min 挑最小——Python 里集合的 < 是「真子集」判断而非全序，两个不可比的同构形态会让 min 的结果随迭代顺序漂移，把本来相似的星座分到不同字母上。正确做法是先转成 tuple(sorted(...)) 再比较。

复杂度

设总星数为 $S$ （ $S \leqslant 100 \times 100$ ，且每星座 $\leqslant 160$ 格）。

洪填每个格子进出栈一次： $O(S)$ 。
每个星座算一次指纹：8 种变换各 $O(\text{块大小})$ ，合计 $O(8S)$ 。
指纹的 dict 操作与字母回写： $O(S)$ 。

总时间 $O(8S) \approx 8 \times 10^4$ 次基本操作，空间 $O(S)$ ，与 C++ 正解同阶。

总结

星座 = 8 连通分量，一次扫描 + 洪填即可全部提取。
「旋转/翻转后形状相同」用 D4 规范形指纹 判等：8 种变换各自平移归一化，取字典序最小形态，判同从两两比对降到一次哈希查找。
字母分配只需 dict.setdefault(指纹, 下一个字母)，与扫描顺序天然一致。
实现陷阱：集合比较是子集偏序，规范化结果必须转有序元组再比大小。

图示解析

官方样例的标号结果

以官方样例（ $23 \times 15$ ）为例，标号后同一字母的星座形状互为旋转/翻转。观察输出中部的三个 c 块和 b 块：它们星数相同、形状相同，只是摆放方向不同，所以共用字母；而星数不同的块永远不会共享字母。

指纹识别的局部演示

取样例里的一个真实例子说明指纹如何把不同方向「折叠」到同一个键上。设某星座的格子为 (0,0) (1,0) (2,1)（一个斜 L）：

D4 变换	变换后点集	平移归一化后
恒等	(0,0) (1,0) (2,1)	(0,0) (1,0) (2,1)
上下翻转	(0,0) (-1,0) (-2,1)	(0,1) (1,1) (2,0)
旋转 $90^\circ$	(0,0) (0,-1) (1,-2)	(0,2) (0,1) (1,0)
……（其余 5 种同理）	……	……

8 个归一化形态中字典序最小的是 (0,0) (0,1) (1,0) 方向的某个序列——无论原星座在天体图的位置和朝向如何，这个最小值都不变，它就是该星座的身份证。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

官方样例的标号结果

指纹识别的局部演示