十六 1402. 星空之夜 (哈希表)

1402. 星空之夜 (哈希表)

思路：整体方法就是使用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();
        }
    }
}