AcWing 1402. 星空之夜(注释版)
原题链接
中等
作者:
__葑茚丶誋憶
,
2024-04-03 22:40:46
,
所有人可见
,
阅读 5
//解决本题需要考虑三个问题
//1.如果找星星 -----flood fill 算法 (只会这一步好吧.)
//2.如何区分星星 -----利用哈希思想,计算每个星群所有点之间的欧几里得距离 然后对比是否相等
//3.如何保证字典序 -----只要搜到星群,按照字典序赋值即可(没有额外增加难度)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=110,M=170;//N表示矩阵范围,M表示星星的数量
const double esp = 1e-8;
char g[N][N];
PII star[M];//用来存每一个星群 每次进行覆盖
double s_hash[30];//用来存放每个星群的哈希值
int n,m;
int x=0;//k表示当前星群内星星的个数
int cnt=0;//cnt表示星群的个数
void dfs(int a,int b)
{
star[x++]={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>=0&&x<n&&y>=0&&y<m&&g[x][y]=='1')
dfs(x,y);
}
}
double get_value(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(int u)
{
//遍历该星群中的每两个点,求出欧几里得距离之和
double sum=0;
for(int i=0;i<u;i++)
for(int j=i+1;j<u;j++)
{
sum+=get_value(star[i],star[j]);
}
return sum;
}
char get_id(int u)//u表示当前星群的星星数量
{
double val=get_hash(u);//获得当前星群的哈希值
//分别与其他清星群比较
for(int i=0;i<cnt;i++)
{
if(abs(s_hash[i]-val)<esp)//浮点数判断是否相等的写法
return 'a'+i;//返回相等星群的哈希值
}
//到这里说明当前星群与其他星群都不相等
s_hash[cnt++]=val;
return 'a'+cnt-1;//返回当前星群的哈希值
}
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')
{
x=0;
dfs(i,j);
char id=get_id(x);//获取当前星群要赋值的字母
for(int k=0;k<x;k++)
{
g[star[k].first][star[k].second]=id;
}
}
}
for(int i=0;i<n;i++)puts(g[i]);
return 0;
}