AcWing 1402 星空之夜

链接: link.
首先根据题意，我们应该先找出所有连通块，这里我们用到的是Flood Fill 算法。
然后我们要判断两连通块形状是否相同（通过旋转或对称可以使连通块变到重合）。这里我们采用哈希存储下不同形状的连通块。我们要保证形状形同的连通块映射到同一个数，且尽量避免冲突。这里我们采用两两之间的欧几里得距离作为哈希函数。

Flood Fill 模板

BFS模板

void bfs(int a,int b)
{
    queue<PAIR> q;
    st[a][b] = true;
    q.push({a,b});

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        a = t.first, b = t.second;
        st[a][b] = true;
        for (a,b) 相邻的点
        {
            (x,y) = (a,b)的邻点
            if (x,y没被遍历过)
            {
                st[x][y] = true;
                q.push(x,y);
            }
        }
    }
}

DFS模板

void DFS(int a,int b)
{
    q[top++] = {a,b};
    Map[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&&Map[x][y]=='1')
                DFS(x,y);
        }
    }
}

题目代码

#include <bits/stdc++.h>

#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 Map[N][N];
pii q[N*N];
int top;

double get_dis(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_dis(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 a,int b)//Flood Fill算法
{
    q[top++] = {a,b};
    Map[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&&Map[x][y]=='1')
                DFS(x,y);
        }
    }
}

int main()
{
    cin>>m>>n;
    for(int i=0; i<n; i++)
        cin>>Map[i];
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(Map[i][j]=='1')
            {
                top = 0;
                DFS(i,j);
                char ch = get_id(get_hash());
                for(int k=0; k<top; k++)
                    Map[q[k].x][q[k].y] = ch;
            }
        }
    }
    for(int i=0; i<n; i++)
        cout<<Map[i]<<endl;
    return 0;
}