1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| import java.io.*;
import java.util.*;
class Main{
public static int N = 100,n,m;
public static char[][] g = new char[N][N],pg = new char[N][N];
public static int[][] stu = new int[N][N];
public static int[] dx = {0,1,0,-1,1,1,-1,-1},dy = {1,0,-1,0,1,-1,1,-1};
public static double[] hash = new double[30];
public static Scanner sc = new Scanner(System.in);
public static List<Pair> bfs(int x,int y){
Pair p = new Pair(x,y);
List<Pair> res = new ArrayList<>();
res.add(p);
Pair[] queue = new Pair[200];
stu[x][y] = 1;
int hh = 0,tt = -1;
queue[++tt] = p;
while(hh <= tt){
Pair u = queue[hh++];
for(int i = 0;i < 8;i++){
int tx = u.x + dx[i],ty = u.y + dy[i];
if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
if(stu[tx][ty] == 1 || g[tx][ty] == '0') continue;
queue[++tt] = new Pair(tx,ty);
res.add(new Pair(tx,ty));
stu[tx][ty] = 1;
}
}
return res;
}
public static int hash(double key){
for(int i = 0;i < 26;i++){
if(hash[i] == -1 || Math.abs(hash[i] - key) < 1e-7) return i;
}
return -1;
}
public static double getHash(List<Pair> list){
double res = 0;
for(int i = 0;i < list.size();i++)
for (int j = i+1;j < list.size();j++){
int x1 = list.get(i).x,x2 = list.get(j).x,y1 = list.get(i).y,y2 = list.get(j).y;
res += Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
return res;
}
public static void print(List<Pair> list,int x){
char t = (char)( 'a' + x);
for(int i = 0;i < list.size();i++) pg[list.get(i).x][list.get(i).y] = t;
}
public static void print(){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
System.out.print(pg[i][j]);
}
System.out.println();
}
}
public static void main(String[] args){
m = sc.nextInt();
n = sc.nextInt();
for(int i = 1;i <= n;i++){
Arrays.fill(pg[i],'0');
String s = sc.next();
for(int j = 1;j <= m;j++)
g[i][j] = s.charAt(j-1);
}
Arrays.fill(hash,-1);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(stu[i][j] == 0 && g[i][j] == '1'){
List<Pair> list = bfs(i, j);
double key = getHash(list);
int value = hash(key);
hash[value] = key;
print(list,value);
}
}
}
print();
}
static class Pair{
int x,y;
public Pair(int x,int y){
this.x = x;
this.y = y;
}
}
}
|
