要点

1. dfs Or bfs 搜连通块并记录
2. 构造哈希函数区分不同的图形
   • 以连通块两两距离之和作为哈希值
3. 步骤
   • 先遍历星图搜连通块，每搜得一整块，计算其哈希，
   • 算得的哈希与已记录的哈希表匹配，有则取得对应的标记字母，无则赋予一个新的标记字母并将该哈希值记录到表中
   • 遍历该连通块，修改星图内容为标记字母

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int w, h, top;  // 宽、高、top辅助当前联通块存放到数组
    static char[][] f = new char[110][1];  // 星图矩阵
    static Point[] p = new Point[170];  // 存放dfs出来的连通块
    static double epsilon = 1e-6;
    static ArrayList<Double> hashArray = new ArrayList<>();  // 存放已记录的hash

    static class Point {
        public int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static double getDistance(Point a, Point b) {  // 求两点距离
        double dx = a.x - b.x, dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    static double getHash() {  // 遍历所有联通块 求两两距离之和 作为hash
        double sum = 0;
        for (int i = 0; i < top; i++) {
            for (int j = i + 1; j < top; j++) {
                sum += getDistance(p[i], p[j]);
            }
        }
        return sum;
    }

    static char getId(double hash) {  // 通过hash求对应的标记字母
        for (int i = 0; i < hashArray.size(); i++) {  // 遍历hash记录表
            if (Math.abs(hash - hashArray.get(i)) < epsilon) {  // 浮点数判断相等
                return (char) (i + 'a'); // 有则返回已记录的标记字母
            }
        }
        hashArray.add(hash);  // 如果没有记录过当前hash 证明是新图像 存hash到记录表里
        return (char) (hashArray.size() - 1 + 'a');  // 返回一个新的标记字母
    }

    static void drawId(char id) {  // 遍历连通块记录数组 把所有块打上对应的标记字母
        for (int i = 0; i < top; i++) {
            f[p[i].x][p[i].y] = id;
        }
        top = 0;  // 重置记录游标 即清空当前记录的连通块
    }

    static void dfs(int x, int y) {
        p[top++] = new Point(x, y);  // 存连通块到记录数组
        f[x][y] = '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 && f[i][j] == '1') {
                    dfs(i, j);
                }
            }
        }
    }

    public static void main(String[] args) {
        w = scanner.nextInt();
        h = scanner.nextInt();
        for (int i = 0; i < h; i++) {
            f[i] = scanner.next().toCharArray();
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (f[i][j] == '1') {
                    dfs(i, j);
                    drawId(getId(getHash()));
                }
                System.out.print(f[i][j]);
            }
            System.out.println();
        }
    }
}