118 lines
3.0 KiB
Java
118 lines
3.0 KiB
Java
import java.io.BufferedReader;
|
|
import java.io.IOException;
|
|
import java.io.InputStreamReader;
|
|
import java.util.*;
|
|
|
|
class Axis {
|
|
int x, y;
|
|
Axis(int x, int y) {
|
|
this.x = x;
|
|
this.y = y;
|
|
}
|
|
}
|
|
|
|
public class _16946 {
|
|
static int N, M;
|
|
static int[][] MAP, groupMAP;
|
|
static boolean[][] visited;
|
|
|
|
static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
|
|
|
|
static int findGroupSize(int x, int y, int group) {
|
|
Queue<Axis> qu = new ArrayDeque<>();
|
|
qu.add(new Axis(x, y));
|
|
|
|
visited[y][x] = true;
|
|
groupMAP[y][x] = group;
|
|
|
|
int size = 1;
|
|
|
|
while(!qu.isEmpty()) {
|
|
Axis now = qu.poll();
|
|
|
|
for(int i=0; i<4; i++) {
|
|
int nx = now.x + dx[i], ny = now.y + dy[i];
|
|
|
|
if(0 <= nx && nx < M && 0 <= ny && ny < N && !visited[ny][nx] && MAP[ny][nx] != 1) {
|
|
visited[ny][nx] = true;
|
|
size++;
|
|
qu.add(new Axis(nx, ny));
|
|
groupMAP[ny][nx] = group;
|
|
}
|
|
}
|
|
}
|
|
|
|
return size;
|
|
}
|
|
|
|
public static void main(String[] args) throws IOException {
|
|
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
|
|
StringTokenizer st = new StringTokenizer(br.readLine());
|
|
|
|
N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
|
|
|
|
MAP = new int[N][M];
|
|
|
|
for(int i=0; i<N; i++) {
|
|
String row = br.readLine();
|
|
for(int j=0; j<M; j++) MAP[i][j] = row.charAt(j) - '0';
|
|
}
|
|
|
|
groupMAP = new int[N][M];
|
|
visited = new boolean[N][M];
|
|
ArrayList<Integer> groupSize = new ArrayList<>();
|
|
int group = 0;
|
|
|
|
for(int i=0; i<N; i++) {
|
|
for(int j=0; j<M; j++) {
|
|
if(visited[i][j] || MAP[i][j] == 1) continue;
|
|
|
|
groupSize.add(findGroupSize(j, i, group++));
|
|
}
|
|
}
|
|
|
|
StringBuilder sb = new StringBuilder();
|
|
|
|
for(int i=0; i<N; i++) {
|
|
for(int j=0; j<M; j++) {
|
|
if(MAP[i][j] == 0) {
|
|
sb.append(0);
|
|
continue;
|
|
}
|
|
|
|
int cnt = 1;
|
|
int[] nearGroups = new int[4];
|
|
int idx = 0;
|
|
|
|
for(int k=0; k<4; k++) {
|
|
int nx = j + dx[k], ny = i + dy[k];
|
|
|
|
if(0 > nx || nx >= M || 0 > ny || ny >= N || MAP[ny][nx] == 1) continue;
|
|
|
|
nearGroups[idx++] = groupMAP[ny][nx];
|
|
}
|
|
|
|
for(int k=0; k<idx; k++) {
|
|
boolean isDup = false;
|
|
|
|
for(int l=0; l<k; l++) {
|
|
if(nearGroups[k] == nearGroups[l]) {
|
|
isDup = true;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if(!isDup) cnt += groupSize.get(nearGroups[k]);
|
|
}
|
|
|
|
sb.append(cnt%10);
|
|
}
|
|
sb.append("\n");
|
|
}
|
|
|
|
|
|
System.out.print(sb);
|
|
|
|
}
|
|
}
|