import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); char[][] s = new char[h][w]; for (int i = 0; i < h; i++) { s[i] = sc.next().toCharArray(); } sc.close(); int inf = 100000000; int[][] d = new int[h][w]; for (int i = 0; i < h; i++) { Arrays.fill(d[i], inf); } List> list = new ArrayList<>(h - 1); List> listb = new ArrayList<>(h - 1); for (int i = 0; i < h - 1; i++) { TreeSet set = new TreeSet<>(); TreeSet setb = new TreeSet<>(); for (int j = 0; j < w; j++) { if (s[i][j] == '.') { set.add(j); } else { setb.add(j); } } list.add(set); setb.add(-1); setb.add(w); listb.add(setb); } PriorityQueue que = new PriorityQueue<>((o1, o2) -> o1.d - o2.d); int h1 = h - 1; for (int j = 0; j < w; j++) { if (s[h1][j] == '.') { d[h1][j] = 0; que.add(new Obj(h1, j, d[h1][j])); } } List remList = new ArrayList<>(); while (!que.isEmpty()) { Obj o = que.poll(); if (d[o.i][o.j] < o.d) { continue; } if (o.i > 0 && s[o.i - 1][o.j] == '.') { int ni = o.i - 1; int end = Math.min(o.j + o.d + 1, listb.get(ni).ceiling(o.j)); TreeSet set = list.get(ni); Set ss = set.subSet(o.j, end); for (int nj : ss) { int alt = o.d; if (d[ni][nj] > alt) { d[ni][nj] = alt; que.add(new Obj(ni, nj, alt)); } remList.add(nj); } set.removeAll(remList); remList.clear(); end = Math.max(o.j - o.d, listb.get(ni).floor(o.j) + 1); ss = list.get(ni).subSet(end, true, o.j, true).descendingSet(); for (int nj : ss) { int alt = o.d; if (d[ni][nj] > alt) { d[ni][nj] = alt; que.add(new Obj(ni, nj, alt)); } remList.add(nj); } set.removeAll(remList); remList.clear(); } int ni = o.i; if (o.j > 0) { int nj = o.j - 1; if (s[ni][nj] == '.') { int alt = o.d + 1; if (d[ni][nj] > alt) { d[ni][nj] = alt; que.add(new Obj(ni, nj, alt)); } } } if (o.j < w - 1) { int nj = o.j + 1; if (s[ni][nj] == '.') { int alt = o.d + 1; if (d[ni][nj] > alt) { d[ni][nj] = alt; que.add(new Obj(ni, nj, alt)); } } } } PrintWriter pw = new PrintWriter(System.out); for (int j = 0; j < w; j++) { pw.println(d[0][j]); } pw.flush(); } static class Obj { int i, j, d; public Obj(int i, int j, int d) { this.i = i; this.j = j; this.d = d; } } }