题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
java 代码
blablabla
import java.util.*;
class Main{
static int id = 0;
static Double[] hash = new Double[26];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int w = sc.nextInt(), h = sc.nextInt();
char[][] matrix = new char[h][w];
sc.nextLine();
for (int i = 0; i < h; i) {
String s = sc.nextLine();
for (int j = 0; j < w; j) {
matrix[i][j] = s.charAt(j) == ‘1’? ‘1’ : ‘0’;
}
}
for (int i = 0; i < h; i) {
for (int j = 0; j < w; j) {
if(matrix[i][j] == ‘1’) {
List[HTML_REMOVED] list = new ArrayList<>();
dfs(‘2’, matrix, i, j, list);
char cur = getID(list);
for (int[] point : list) matrix[point[0]][point[1]] = cur;
}
}
}
for (int i = 0; i < h; i) {
for (int j = 0; j < w; j) {
System.out.print(matrix[i][j]);
}
System.out.println();
}
}
public static void dfs(char temp, char[][] matrix, int row, int col, List<int[]> list) {
if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || matrix[row][col] != '1') return;
list.add(new int[]{row, col});
matrix[row][col] = temp;
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i == 0 && j == 0) continue;
dfs(temp, matrix, row + i, col + j, list);
}
}
}
public static double getDis(int[] pointA, int[] pointB) {
double dx = pointB[0] - pointA[0], dy = pointA[1] - pointB[1];
return Math.sqrt(dx * dx + dy * dy);
}
public static double getHash(List<int[]> list) {
double res = 0;
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
res += getDis(list.get(i), list.get(j));
}
}
return res;
}
public static char getID(List<int[]> list) {
double res = getHash(list);
for (int i = 0; i < 26; i++) {
// 因为只有一个会得到res = 0.0 double数组默认为0 然后会得到res = hash[i] < 1e-6 以为找到了
//但id没有变化还是停在原来让人误以为是找到了之前存在的实际上是新的 要hash[id++] = res;return (char) (id - 1 + 'a')
// 没有找到旧的不能return (char) ('a' + i) 为了不出现这种情况我们把double变成Double 加个判定hash[i] != null
if (hash[i] != null && Math.abs(res - hash[i]) < 1e-6) {
return (char) ('a' + i);
}
}
hash[id++] = res;
return (char) (id - 1 + 'a');
}
}