AcWing 1402. 星空之夜 （flood fill+图哈希）

AcWing 1402. 星空之夜

图的哈希：
图中的每两个点两两计算欧几里得距离，再加和。则这个图不管怎么旋转，镜像，都会映射到同一个hash值。

用pair数组pair<int,int> q[]去存下dfs得到的一个图的所有点

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;
const int N = 110;
const double eps = 1e-6;
char g[N][N];
typedef pair<int, int> PII;
PII q[N * N];

int n, m;
int top;

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

double get_hash() {
    double sum = 0;
    for (int i = 0; i < top; i++) {
        for (int j = i + 1; j < top; j++) {
            sum += get_dist(q[i], q[j]);
        }
    }
    return sum;
}

char get_id(double key) {
    static double hash[N];
    static int id = 0;
    for (int i = 0; i < id; i++) {
        if (fabs(key - hash[i]) < eps)
            return i + 'a';
    }
    hash[id++] = key;
    return id - 1 + 'a';
}

void dfs(int a, int b) {
    q[top++] = {a, b};
    g[a][b] = '0';

    for (int i = a - 1; i <= a + 1; i++) {
        for (int j = b - 1; j <= b + 1; j++) {
            if (i == a && j == b)continue;
            if (i >= 0 && i < n && j >= 0 && j < m && g[i][j] == '1')
                dfs(i, j);
        }
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i++)cin >> 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 c = get_id(get_hash());
                for (int i = 0; i < top; i++) {
                    int a = q[i].x, b = q[i].y;
                    g[a][b] = c;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << g[i] << endl;
    }
    
    return 0;
}