AcWing 1402. 星空之夜 1月28

AcWing 1402. 星空之夜 1月28

题意：

一个星群是指一组非空的在水平，垂直或对角线方向相邻的星星的集合。
一个星群不能是一个更大星群的一部分。
星群可能是相似的。
如果两个星群的形状、包含星星的数目相同，那么无论它们的朝向如何，都认为它们是相似的。
给定一个夜空二维矩阵，请你将其中的所有星群用小写字母进行标记，标记时相似星群用同一字母，不相似星群用不同字母。

题解：

本题的关键在于如何判断两个星群是否相似，也就是如何分配字母的问题。题目说了相似说明两个星群形状一样，与方向无关，形状这一特征我们可以从每个星星与其他星星的距离和来表示
对于每一个星群，计算其内部距离和，然后看之前是否出现过，出现过则给之前的字母，若没出现则根据出现顺序赋予字母

代码：

代码思路肯定是对的，但是不知道哪错了

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
int dy[9]={-1,0,1,-1,1,-1,0,1},dx[9]={-1,-1,-1,0,0,1,1,1};
const int maxn=600;
char a[maxn][maxn];
char newa[maxn][maxn];
int w,h;
vector<pair<int,int> >c; 
vector<ll>mapp;
void dfs(int x,int y)
{
    a[x][y]='0';
    c.push_back({x,y});
    for(int i=0;i<=7;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(a[tx][ty]=='0'||tx>h||tx<=0||ty>w||ty<=0)continue;
        dfs(tx,ty);
    }
}
ll getsum()
{
    ll sum=0;
    for(int i=0;i<c.size();i++)
    {
        for(int j=i+1;j<c.size();j++)
        {
            sum+=(c[i].first-c[j].first)*(c[i].first-c[j].first)+(c[i].second-c[j].second)*(c[i].second-c[j].second);
        }
    }
    return sum;
}
char check(ll sum)
{
    for(int i=0;i<mapp.size();i++)
    {
        if(mapp[i]==sum)return (char)('a'+i);
    }
    char neww='a'+mapp.size();
    mapp.push_back(sum);
    return neww;
}
void fill(char x)
{
    for(int i=0;i<c.size();i++)
    {
        newa[c[i].first][c[i].second]=x;
    }
}
int main()
{
    memset(newa,'0',sizeof(newa));
    cin>>w>>h;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>a[i][j];
        }
        //char ch=getchar();
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            if(a[i][j]=='1')
            {
                dfs(i,j);
                ll sum=getsum();
                char x=check(sum);
                fill(x);
                c.clear();
            }
        }
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            printf("%c",newa[i][j]);
        }
        printf("\n");
    }
}