【思路】
Flood Fill算法(dfs函数)判断连通块 利用hash函数解决相似星群,该hash函数为每个星群两两星星之间的直线距离之和。
import java.io.*;
import java.lang.Math;
class node{
int x, y;
public node(int xx, int yy){
this.x = xx;
this.y = yy;
}
}
public class Main{
static int N = 110;
static int n, m;
static int sum;
//星群矩阵
static char [][] g = new char[N][N];
//q数组存放某个星群中星星的坐标 该星群有sum个星星
static node[] q = new node[ N * N];
static double []hash = new double[30];
static double esp = 1E-6;
//当前使用的字母为'a'
static int t = 0;
//八个方向
static int[][]dir = {{-1, 0},{-1, 1},{0, 1},{1, 1},
{1, 0},{1, -1},{0, -1},{-1, -1}};
public static void dfs(int x, int y){
//标记为走过
g[x][y] = '0';
//记录星群中的星星
q[sum ++] = new node(x, y);
for(int i = 0; i < 8; i++){
int nx = x +dir[i][0], ny = y + dir[i][1];
if( nx < 0 || nx >= m || ny < 0 || ny >= n || g[nx][ny] == '0') continue;
dfs(nx, ny);
}
}
//计算星群中两颗星星的距离
public static double get_dist(int i, int j){
double dx = q[i].x - q[j].x;
double dy = q[i].y - q[j].y;
return Math.sqrt(dx * dx + dy * dy);
}
//根据每个星群的两两星星之间的距离计算每个星群的哈希值
//该Hash值保证:1、相似(形状、包含星星的数目相同、朝向可能不一致)的星群映射到同一个哈希值
//2、 避免哈希冲突
public static double get_hash(){
double ans = 0;
for(int i = 0; i < sum; i++)
for(int j = i + 1; j < sum; j++)
ans += get_dist(i, j);
return ans;
}
//根据计算的哈希值返回字母
public static char get_id(double ans){
for(int i = 0; i < t; i++)
//哈希值相同则为同一星群
if( Math.abs(ans - hash[i]) < esp)//此处为加 i (晕死了 写成了加tdebug了半天)
return (char) ('a' + i);
hash[t ++] = ans;
return (char)('a' + t - 1);
}
public static void main(String aregs[])throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bf.readLine());
m = Integer.parseInt(bf.readLine());
for(int i = 0; i < m; i++) g[i] = bf.readLine().toCharArray();
for(int i = 0; i < m; i++)
for(int j = 0; j < n ; j++){
if(g[i][j] == '1') {
//星群中星星的数量清零
sum = 0;
dfs(i, j);
char c = get_id(get_hash());
//将星群中星星标记
for(int k = 0; k < sum; k++) g[ q[k].x ][ q[k].y ] = c;
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n ; j++)
System.out.print(g[i][j]+"");
System.out.println();
}
}
}