星空之夜

夜空深处，闪亮的星星以星群的形式出现在人们眼中，形态万千。

一个星群是指一组非空的在水平，垂直或对角线方向相邻的星星的集合。

一个星群不能是一个更大星群的一部分。

星群可能是相似的。

如果两个星群的形状、包含星星的数目相同，那么无论它们的朝向如何，都认为它们是相似的。

通常星群可能有 $8$ 种朝向，如下图所示：

现在，我们用一个二维 $01$ 矩阵来表示夜空，如果一个位置上的数字是 $1$，那么说明这个位置上有一个星星，否则这个位置上的数字应该是 $0$。

给定一个夜空二维矩阵，请你将其中的所有星群用小写字母进行标记，标记时相似星群用同一字母，不相似星群用不同字母。

标注星群就是指将星群中所有的 $1$ 替换为小写字母。

输入格式

第一行包含一个整数 $W$，表示矩阵宽度。

第二行包含一个整数 $H$，表示矩阵高度。

接下来 $H$ 行，每行包含一个长度为 $W$ 的 $01$ 序列，用来描述整个夜空矩阵。

输出格式

输出标记完所有星群后的二维矩阵。

用小写字母标记星群的方法很多，我们将整个输出读取为一个字符串，能够使得这个字符串字典序最小的标记方式，就是我们想要的标记方式。

输出这个标记方式标出的最终二维矩阵。

数据范围

$0\leq W,H\leq 100$,
$0\leq 星群数量 \leq 500$,
$0\leq 不相似星群数量 \leq26$,
$1\leq 星群中星星的数量 \leq160$

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
23
15
10001000000000010000000
01111100011111000101101
01000000010001000111111
00000000010101000101111
00000111010001000000000
00001001011111000000000
10000001000000000000000
00101000000111110010000
00001000000100010011111
00000001110101010100010
00000100110100010000000
00010001110111110000000
00100001110000000100000
00001000100001000100101
00000001110001000111000

输出样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a000a0000000000b0000000
0aaaaa000ccccc000d0dd0d
0a0000000c000c000dddddd
000000000c0b0c000d0dddd
00000eee0c000c000000000
0000e00e0ccccc000000000
b000000e000000000000000
00b0f000000ccccc00a0000
0000f000000c000c00aaaaa
0000000ddd0c0b0c0a000a0
00000b00dd0c000c0000000
000g000ddd0ccccc0000000
00g0000ddd0000000e00000
0000b000d0000f000e00e0b
0000000ddd000f000eee000

解题思路

  • 首先显然是找连通块，可以使用floodfill算法；

  • 其次如何判断一个图形是否相似：相似包括对称、旋转，或者二者的组合；

  • 一般的，计算连通块任意两点间的欧几里得距离之和用作哈希值；

  • 注意，这是一种近似算法，可能会发生哈希冲突，可以多个哈希减小冲突可能性。

AC代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;


typedef pair<int, int> PII;

#define x first
#define y second

const int N = 110, M = 170;
const double eps = 1e-8;

int n, m;
char g[N][N];
PII s[M];
int top = 0, cnt = 0;
double hv[30];

void dfs(int x,int y) {
    s[top++] = {x,y};
    g[x][y] = '0';
    for(int i = x - 1; i <= x + 1; ++ i)
        for(int j = y - 1; j <= y + 1; ++ j) {
            if (i >= 0 && i < n && j >= 0 && j < m && g[i][j] == '1'){
                dfs(i,j);
            }
        }
}

double get_hash() {
    double key = 0;
    for(int i = 0; i < top; ++ i)
        for(int j = 0; j < i; ++ j) {
            int a = s[i].x - s[j].x,b = s[i].y - s[j].y;
            key += sqrt(a * a + b * b);
        }
    return key;
}

char get_id() {
    double key = get_hash();
    for(int i = 0; i < cnt; ++ i)
        if(abs(hv[i] - key) < eps)
            return i + 'a';
    hv[cnt ++] = key;
    return cnt - 1 + 'a';
}

int main() {
    scanf("%d%d",&m,&n);
    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(g[i][j] == '1') {
             top = 0;
             dfs(i,j);
             char id = get_id();
             for(int u = 0; u < top; ++ u)
                g[s[u].x][s[u].y] = id;
        }
    for(int i = 0; i < n; ++ i) puts(g[i]);
    return 0;
}