Acwing 1402.星空之夜

这题思路很好看，但实现却很难，用到了欧几里得距离来代表一个星群的形状，对一个星群，任意两点（从这些可以组成星群的点中抽取两个点(相当于集合））之间的距离之和
就好比有1、2、3、4、5五个点
找1-2 1-3 1-4 1-5 2-3 2-4 2-5 3-4 3-5 4-5的距离之和。

g代表一个形状对应的值
标记方法1.  g=d(ai-aj)(0<=i<j<n)
标记方法2.  g=d(ai-aj)(0<=i<=j<n)

老师讲解网站

https://www.acwing.com/video/2330/

代码（来回debug了很长，结果思路没错，n,m输入是不是对应输入（题目中给的是m,n)
代码如下

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define x first
#define y second
typedef  pair<int,int> PII;
const int N = 110 ;
const double eps=1e-6;
int n , m ,top;
double hash1[30] ;
int id;
char g[N][N] ;
PII lc[N*N];
void dfs(int a,int b)
{
    lc[top++]={
    a,b};g[a][b]='g';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(0<=i&&0<=j&&i<n&&j<m&&g[i][j]=='1')dfs(i,j);}return;
}
double get_dis(PII a,PII b)
{
    double ux=a.x-b.x;double uy=a.y-b.y;double sum=sqrt(ux*ux+uy*uy);return sum;
}
double get_hash()
{
    double sum=0;for(int i=0;i<top;i++)for(int j=i+1;j<top;j++){
    sum+=get_dis(lc[i],lc[j]);}return sum;
}
char get_id(double g)
{
    for(int i=0;i<id;i++)if(fabs(hash1[i]-g)<eps)return 'a'+i;hash1[id]=g;id++;return 'a'+id-1;
}
int main(void)
{
    cin>>m>>n;for(int i = 0;i < n;i++) cin>>g[i];for(int i=0;i<n;i++)for(int c=0;c<m;c++)if(g[i][c]=='1'){
    top=0;dfs(i,c);char s=get_id(get_hash());for(int z=0;z<top;z++)g[lc[z].x][lc[z].y]=s;}for(int i=0;i<n;i++) cout<<g[i]<<endl;}