import sys from collections import deque def debug(x, table): for name, val in table.items(): if x is val: print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr) return None def solve(): W, H = map(int, input().split()) C = [list(input()) for i in range(H)] col = 1 for i in range(H): for j in range(W): if C[i][j] == '#': C[i][j] = 0 elif C[i][j] == '.': bfs_color(W, H, C, i, j, col) col += 1 else: pass for i in range(H): print(*C[i]) cave1 = [] cave2 = [] for i in range(H): for j in range(W): if C[i][j] == 1: cave1.append((i, j)) elif C[i][j] == 2: cave2.append((i, j)) min_d = 1000 for a in cave1: for b in cave2: min_d = min(min_d, dist(a, b) - 1) print(min_d) def dist(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) def bfs_color(W, H, C, i, j, col): nxt = deque([(i, j)]) while nxt: y, x = nxt.pop() C[y][x] = col if x - 1 >= 0 and C[y][x-1] == '.': nxt.append((y, x-1)) if x + 1 < W and C[y][x+1] == '.': nxt.append((y, x+1)) if y - 1 >= 0 and C[y-1][x] == '.': nxt.append((y-1, x)) if y + 1 < H and C[y+1][x] == '.': nxt.append((y+1, x)) return None if __name__ == '__main__': solve()