蓝桥集训之星空之夜

蓝桥集训之星空之夜

• 核心思想：哈希 + Flood Fill

  • 将每个连通块找出 并求其中每两个坐标的距离 之和
  • 这个距离就是一张图的哈希值 再用这个哈希值找对应的字母

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int N = 110;
    const double eps = 1e-8;
    #define x first
    #define y second
    typedef pair<int,int> PII;
    
    PII q[N*N];
    char g[N][N];
    int n,m;
    int top;
    int id;
    
    double get_dist(PII a,PII b)  //两点距离
    {
        double dx = a.x - b.x;
        double 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];  //静态变量
        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 a,int b)
    {
        q[top++] = {a,b};  //一个连通块所有点
        g[a][b] = '0';
        for(int x=a-1;x<=a+1;x++)
            for(int y=b-1;y<=b+1;y++)
            {
                if(x == a && y ==b) continue;
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1')
                    dfs(x,y);
            }
    }
    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 k=0;k<top;k++)
                    {
                        g[q[k].x][q[k].y] = c;
                    }
                }
            }
        }
        for(int i=0;i<n;i++) cout<<g[i]<<endl;
        return 0;
    }