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");
	}
}