【ACWing】1402. 星空之夜

题目地址：

https://www.acwing.com/problem/content/1404/

给定一个 m m m行 n n n列的二维 0 − 1 0-1 0−1矩阵 A A A，考虑所有的 1 1 1的八连通块，要求将所有的形状相同的八连通块标记为相同的小写字母，并且使得输出矩阵的时候，矩阵字典序最小。两个连通块形状相同是指，旋转 90 ° , 180 ° , 270 ° 90\degree, 180\degree, 270\degree 90°,180°,270°或者左右镜像翻转、上下镜像翻转之后能重合。

数据范围：
0 ≤ m , n ≤ 100 0\le m,n\le 100 0≤m,n≤100
0 ≤ s ≤ 500 0\le s\le 500 0≤s≤500
0 ≤ d ≤ 26 0\le d\le 26 0≤d≤26
1 ≤ t ≤ 160 1\le t\le 160 1≤t≤160
s s s为 1 1 1连通块数量， d d d为不同的连通块数量， t t t是每个 1 1 1连通块 1 1 1的数量

思路是哈希。对于一个八连通块 C C C，我们定义其哈希值为 ∑ ( x 1 , y 1 ) , ( x 2 , y 2 ) ∈ C , ( x 1 , y 1 ) ≠ ( x 2 , y 2 ) ∣ A [ x 1 ] [ y 1 ] − A [ x 2 ] [ y 2 ] ∣ 2 \sqrt{\sum_{(x_1,y_1),(x_2,y_2)\in C,(x_1,y_1)\ne (x_2,y_2)}|A[x_1][y_1]-A[x_2][y_2]|^2} (x1​,y1​),(x2​,y2​)∈C,(x1​,y1​)​=(x2​,y2​)∑​∣A[x1​][y1​]−A[x2​][y2​]∣2 ​我们可以一行一行，每行从左到右遍历，通过DFS搜集每个 1 1 1连通块的坐标，求得其哈希值，然后看一下这个哈希值是否出现过（这里哈希值是double类型的，不能直接用==，而要做差看是否小于一个很小数），如果出现过就标记为之前给它配的那个记号，否则给它以新的标记，按照顺序标记为 a b c d . . . abcd... abcd...。代码如下：

#include <iostream>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;
const double eps = 1e-6;

int n, m;
char g[N][N];
PII q[N * N];

double get_dist(PII a, PII b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// 算一下当前q数组里存的1连通块的哈希值
double get_hash(int size) {
    double sum = 0;
    for (int i = 0; i < size; i++)
        for (int j = i + 1; j < size; j++)
            sum += get_dist(q[i], q[j]);
    return sum;
}

// 根据这个哈希值，返回其应该被标记为什么字母
char get_id(double key) {
    static double hash[30];
    static int id = 0;
    for (int i = 0; i < id; i++) 
    	// 如果该哈希值已存在，则返回之前给它配的那个字母
        if (fabs(hash[i] - key) < eps)
            return i + 'a';
    // 否则将该哈希值加入数组，并返回下一个还没使用的字母
    hash[id++] = key;
    return id - 1 + 'a';
}

void dfs(int x, int y, int& size) {
    q[size++] = {x, y};
    g[x][y] = '0';
    for (int a = x - 1; a <= x + 1; a++) 
        for (int b = y - 1; b <= y + 1; b++) {
            if (a == x && b == y) continue;
            if (0 <= a && a < m && 0 <= b && b < n && g[a][b] == '1')
                dfs(a, b, size);
        }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> g[i];

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j] == '1') {
                int size = 0;
                dfs(i, j, size);
                char c = get_id(get_hash(size));
                for (int k = 0; k < size; k++) 
                    g[q[k].x][q[k].y] = c;
            }

    for (int i = 0; i < m; i++) cout << g[i] << endl;

    return 0;
}

时空复杂度 O ( m n ) O(mn) O(mn)。