package practice;
import java.util.*;
// BFS, baseCode
// 시작 위치ì—ì„œ ê° ìœ„ì¹˜ë§ˆë‹¤ ê°€ëŠ”ë° í•„ìš”í•œ ì´ë™ 횟수(1ë¡œ ëœ ê³³ë§Œ ì´ë™í• 수 있ìŒ)
public class Main6 {
static int grid[][];
static int dist[][];
static boolean visited[][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
grid = new int[n][m];
// 기준 ì 으로 부터 거리 ì°¨ì´(ì‹œê°„ì´ ë ìˆ˜ë„ ìžˆë‹¤)
dist = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = sc.nextInt();
}
}
Queue qx = new LinkedList<>();
Queue qy = new LinkedList<>();
int startx, starty;
// ë°©í–¥
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
startx = starty = 1;
qx.add(startx);
qy.add(starty);
dist[startx][starty] = 0;
// 시작ì trueë¡œ 시작하는 경우 ìžˆê³ ê·¸ë ‡ì§€ ì•Šì€ ê²½ìš° 있다
// 11403 ì—ì„ ì‹œìž‘ì true하지 않는다
visited[startx][starty] = true;
while (!qx.isEmpty()) {
int nowx = qx.poll();
int nowy = qy.poll();
for (int i = 0; i < 4; i++) {
int nextx = nowx + dx[i];
int nexty = nowy + dy[i];
// 조건 3개
// 범위 벗어난 곳
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) {
continue;
}
// 갈 수 없는 곳
if (grid[nextx][nexty] == 0) {
continue;
}
// ì´ë¯¸ 방문한 ê³³
if (visited[nextx][nexty]) {
continue;
}
// 대개 3ê°œ. distê°’ 넣기, visited ë°°ì—´ true 만들기. qì— ë‹¤ìŒ ê°’ 집어 넣기
dist[nextx][nexty] = dist[nowx][nowy] + 1;
visited[nextx][nexty] = true;
qx.add(nextx);
qy.add(nexty);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
}