AcWing 1402. 星空之夜(星群中两两距离之和来标记星群形状)
原题链接
中等
作者:
半透明の微笑
,
2024-04-08 16:49:30
,
所有人可见
,
阅读 5
import java.io.*;
import java.util.*;
public class Main{
static int N = 110;
static char[][] g = new char[N][N];
static PII[] q = new PII[N * N];
static double[] hashVals = new double[N];
static double eps = 1e-9;
static int w, h;
static int top, cnt;
static void dfs(int x,int y){
q[top ++] = new PII(x, y);//把星群中的星星存到q数组中
g[x][y] = '0';//置0,否则深搜会无限循环
for(int i = x - 1; i <= x + 1; i ++){
for(int j = y - 1; j <= y + 1; j ++){
if(i >= 0 && i < h && j >= 0 && j < w && g[i][j] == '1'){
dfs(i, j);
}
}
}
}
static char get_id(){
double hash = get_hash();//根据星群中两两星星之间的距离和来标记这个星群形状
for(int i = 0; i < cnt; i ++){
//如果当前星群的形状已经存在,返回原有标记
if(Math.abs(hash - hashVals[i]) < eps){
return (char)('a' + i);
}
}
////如果当前星群的形状不存在,创建标记并返回
hashVals[cnt ++] = hash;
return (char)('a' + cnt - 1);
}
static double get_hash(){
double dis = 0;
for(int i = 0; i < top; i ++){
for(int j = 0; j < i; j ++){
dis += get_dis(i, j);
}
}
return dis;
}
static double get_dis(int a, int b){
int x1 = q[a].x;
int y1 = q[a].y;
int x2 = q[b].x;
int y2 = q[b].y;
return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
w = Integer.parseInt(br.readLine());
h = Integer.parseInt(br.readLine());
//读取数据
for(int i = 0; i < h; i ++){
char[] c = br.readLine().toCharArray();
for(int j = 0; j < w; j ++){
g[i][j] = c[j];
}
}
//遍历
for(int i = 0; i < h; i ++){
for(int j = 0; j < w; j ++){
//找到"1"就把跟这个"1"所在星群找出来
if(g[i][j] == '1'){
top = 0;//记录当前星群中的星星数
dfs(i, j);//深搜找当前星群所有星星
char id = get_id();//标记当前星群
for(int k = 0; k < top; k ++){
g[q[k].x][q[k].y] = id;
}
}
}
}
for(int i = 0; i < h ; i ++){
for(int j = 0; j < w; j ++){
System.out.print(g[i][j]);
}
System.out.println();
}
}
}
class PII{
int x;
int y;
public PII(int x, int y){
this.x = x;
this.y = y;
}
}