AcWing 1402. 星空之夜-- Java
原题链接
中等
作者:
Jiang锋时刻
,
2021-02-02 22:51:47
,
所有人可见
,
阅读 382
Java 代码
import java.util.*;
import java.io.*;
public class Main {
static List<Double> hash = new ArrayList<>();
static List<int[]> q = new ArrayList<>();
static int col;
static int row;
static char[][] g;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 指定星图的行和列
col = sc.nextInt();
row = sc.nextInt();
// 用g存储整个星图
g = new char[row][col];
for(int i = 0; i < row; i++) {
String str = sc.next();
g[i] = str.toCharArray();
}
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
// 如果当前坐标是星星
if(g[i][j] == '1') {
q.clear();
dfs(i, j);
// 获取星图的hash值
double val = get_hash();
// 不同hash值映射为字符
char c = get_char(val);
for(int[] k: q) {
int a = k[0];
int b = k[1];
g[a][b] = c;
}
}
}
}
for(int i = 0; i < row; i++) {
System.out.println(g[i]);
}
}
// 遍历坐标[x, y], 将其相接触(8个方向)的星云存储在同一个列表中
public static void dfs(int x, int y) {
q.add(new int[]{x, y});
g[x][y] = '0';
// 这里就是相邻的8个表格
for(int i = x - 1; i <= x + 1; i++) {
for(int j = y - 1; j <= y + 1; j++) {
if(i >= 0 && i < row && j >= 0 && j <col &&g[i][j] == '1') {
dfs(i, j);
}
}
}
}
// 计算星图的hash值
// 用星图中任意两个坐标之间的距离之和来表示该星图的hash值
// 虽然也存在不同图形有相同hash值的情况, 但是概率很低很低, 可以忽略
public static double get_hash() {
double res = 0;
for(int i = 0; i < q.size(); i++) {
for(int j = 0; j < q.size(); j++) {
res += get_dist(q.get(i), q.get(j));
}
}
return res;
}
// 不同hash值映射为字符
public static char get_char(double val) {
for(int i = 0; i < hash.size(); i++) {
// 如果当前hash值和列表中的元素值相差很小(1e-6)
// 则直接返回该元素对应的字符
if(Math.abs(val - hash.get(i)) < 1e-6) {
return (char)((i) + 'a');
}
}
// 如果没有, 则添加到列表中, 并返回对应的字符
hash.add(val);
return (char)((hash.size() - 1) + 'a');
}
// 计算两点间的距离
public static double get_dist(int[] a, int[] b) {
return Math.sqrt((a[0] -b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
}