【题目链接】1402. 星空之夜 - AcWing题库
夜空深处,闪亮的星星以星群的形式出现在人们眼中,形态万千。
一个星群是指一组非空的在水平,垂直或对角线方向相邻的星星的集合。
一个星群不能是一个更大星群的一部分。
星群可能是相似的。
如果两个星群的形状、包含星星的数目相同,那么无论它们的朝向如何,都认为它们是相似的。
通常星群可能有 8 种朝向,如下图所示:
现在,我们用一个二维 01矩阵来表示夜空,如果一个位置上的数字是 1,那么说明这个位置上有一个星星,否则这个位置上的数字应该是 0。
给定一个夜空二维矩阵,请你将其中的所有星群用小写字母进行标记,标记时相似星群用同一字母,不相似星群用不同字母。
标注星群就是指将星群中所有的 1 替换为小写字母。
输入样例:
23
15
10001000000000010000000
01111100011111000101101
01000000010001000111111
00000000010101000101111
00000111010001000000000
00001001011111000000000
10000001000000000000000
00101000000111110010000
00001000000100010011111
00000001110101010100010
00000100110100010000000
00010001110111110000000
00100001110000000100000
00001000100001000100101
00000001110001000111000
输出样例:
a000a0000000000b0000000
0aaaaa000ccccc000d0dd0d
0a0000000c000c000dddddd
000000000c0b0c000d0dddd
00000eee0c000c000000000
0000e00e0ccccc000000000
b000000e000000000000000
00b0f000000ccccc00a0000
0000f000000c000c00aaaaa
0000000ddd0c0b0c0a000a0
00000b00dd0c000c0000000
000g000ddd0ccccc0000000
00g0000ddd0000000e00000
0000b000d0000f000e00e0b
0000000ddd000f000eee000
样例解释
样例对应的星空图如下:
答案对应的标记后星空图如下:
【代码及详细注释】
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const double eps=1e-8;
const int N=150;
char mp[N][N];
PII q[200];
int n,m,cnt=0,top;//top用于存储每个星群中点的数量
double hash_val[30];
bool check(int x,int y)
{
if(x<0||x>=n||y<0||y>=m) return false;//下标越界
else if(mp[x][y]=='0') return false;//已经遍历过或者不是星群
return true;
}
void dfs(int x,int y)//找出当前的连通块
{
q[top++]={x,y};//存储每个星群中的点
mp[x][y]='0';//进行标记防止重复遍历
for(int i=x-1;i<=x+1;i++)
{
for(int j=y-1;j<=y+1;j++)
{
if(check(i,j))//判断位置是否是星群中的一点及位置是否合法
dfs(i,j);//继续深搜遍历
}
}
}
double get_dist(int a,int b)
{
PII aa=q[a],bb=q[b];
double xx=aa.first-bb.first;
double yy=aa.second-bb.second;
return sqrt(xx*xx+yy*yy);
}
double get_hash()
{
double ans=0;
for(int i=0;i<top;i++)
{
for(int j=0;j<i;j++)
ans+=get_dist(i,j);//获取两个点的欧几里得距离值
}
return ans;//返回这个星群映射出的所有点之间的距离值
}
char get_id()
{
double val=get_hash();
for(int i=0;i<cnt;i++)//从已有的星群中查找是否有一样的
{
if(abs(val-hash_val[i])<eps)
return 'a'+i;
}
hash_val[cnt++]=val;//是一个新的星群
return 'a'+cnt-1;
}
int main()
{
cin>>m>>n;
for(int i=0;i<n;i++) scanf("%s",mp[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(mp[i][j]=='1')//出现了一个新的星群
{
top=0;
dfs(i,j);
char id=get_id();//获取当前星群的编号
for(int k=0;k<top;k++)
mp[q[k].first][q[k].second]=id;//对星群中所有的点编号
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cout<<mp[i][j];
cout<<endl;
}
return 0;
}