思路:整体方法就是使用DFS找出所有星群,难点是判断星群是否相似,这里是通过累加星群内每两点之间的距离作为哈希值判断是否相似。
import java.util.*;
public class Main {
private static final double eps = 1e-8;
private static int W, H;
private static char[][] g;
private static int top = 0, cnt = 0;
private static int[][] q = new int[160][2];
private static double[] hashVal = new double[30];
private static void dfs(int a, int b) {
q[top++] = new int[]{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 < H && y >= 0 && y < W && g[x][y] == '1') {
dfs(x, y);
}
}
}
}
private static double getDist(int[] a, int[] b) {
double dx = a[0] - b[0];
double dy = a[1] - b[1];
return Math.sqrt(dx * dx + dy * dy);
}
private static double getHashVal() {
double sum = 0;
for (int i = 0; i < top; i++) {
for (int j = 0; j < i; j++) {
sum += getDist(q[i], q[j]);
}
}
return sum;
}
private static char getId() {
double val = getHashVal();
for (int i = 0; i < cnt; i++) {
if (Math.abs(hashVal[i] - val) < eps) {
return (char)('a' + i);
}
}
hashVal[cnt++] = val;
return (char)('a' + cnt - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
W = sc.nextInt();
H = sc.nextInt();
g = new char[H][W];
sc.nextLine();
for (int i = 0; i < H; i++) {
g[i] = sc.nextLine().toCharArray();
}
for(int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (g[i][j] == '1') {
top = 0;
dfs(i, j);
char id = getId();
for (int k = 0; k < top; k++) {
g[q[k][0]][q[k][1]] = id;
}
}
}
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
System.out.print(g[i][j]);
}
System.out.println();
}
}
}
标签:星空,int,double,private,char,++,static,哈希,1402
From: https://www.cnblogs.com/he0707/p/18096804/lanqiaobei16