AcWing 1402. 星空之夜
原题链接
中等
作者:
liebe_1
,
2024-03-30 11:19:57
,
所有人可见
,
阅读 9
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N = 110, M = 170;//M: 最大星星数量, N:矩阵最大行和列
const double eps = 1e-8;
int n,m;
char g[N][N];//
PII q[M];//星星坐标
int top = 0,cnt = 0;//当前星群的星星数量,当前星群的数量
double hash_val[30];//星群的哈希值,也就是将星群转化成浮点数后的,星群对应的浮点数
void dfs(int a, int b) {
q[top++] = {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 && y >= 0 && x < n && y < m && g[x][y] == '1'){
dfs(x,y);
}
}
}//建立一个九宫格来判断上下左右对角线有没有星星,假如有就遍历这个星星
}
double get_dist(PII &a,PII &b) {
double dx = a.x-b.x,dy = a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
double get_hash() {
double sum = 0;
for(int i = 0; i < top; i++) {//5 00 10 20 21 30 31 32 40 41 42 43 应该可以修改
//也可以修改成for(int i = top-1; i >= 0; i++)
for(int j = 0; j < i; j++) {
sum += get_dist(q[i],q[j]);//该星群的第i个星星和第j个星星之间的距离
}
}
return sum;
}//计算当前星群的哈希值(所有点之间的距离之和)
char get_id() {
double val = get_hash();//找到该星群的哈希值
for(int i = 0; i < cnt; i++) {
if(abs(hash_val[i]-val)<eps)return 'a'+i;
}//判断之前是否出现过,浮点数比较(不能直接判断A==B,需要计算两者的差值的绝对值小于一个很小的值eps)
//假如没有出现过,就存下来
hash_val[cnt++] = val;
return 'a'+cnt-1;//上一个语句加一了,但是第cnt个,所以这里要减一
}
int main() {
scanf("%d%d" , &m,&n);
for(int i = 0; i < n; i++)scanf("%s",g[i]);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(g[i][j] == '1'){
top = 0;//新的星群,清空星星数量
dfs(i,j);
char id = get_id();//遍历结束求当前星群的id
for(int k = 0; k < top; k++) {
g[q[k].x][q[k].y] = id;
}//将该星群的字符赋值成对应字母
}
}
}
for(int i = 0; i < n; i++)puts(g[i]);
return 0;
}