AtCoder Grand Contest 033 - Darker and Darker

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is `#` if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is `.` if that square is white.

We will repeatedly perform the following operation until all the squares are black:

* Every white square that shares a side with a black square, becomes black.



Find the number of operations that will be performed. The initial grid has at least one black square.

Constraints

* 1 \leq H,W \leq 1000
* A_{ij} is `#` or `.`.
* The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:


H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}


Output

Print the number of operations that will be performed.

Examples

Input

3 3
...
.#.
...


Output

2


Input

6 6
..#..#
......
..#..
......
.#....
....#.


Output

3

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import deque
from itertools import chain
(H, W) = map(int, input().split())
G = chain.from_iterable([[s == '#' for s in input()] for _ in range(H)])
dist = [0] * (H * W)
B = deque([i for (i, g) in enumerate(G) if g])
visited = set(B)
while B:
	vij = B.pop()
	for dij in (W, -W, 1, -1):
		nij = vij + dij
		if dij == 1 and (not nij % W) or (dij == -1 and (not (nij + 1) % W)) or (not 0 <= nij < H * W) or (nij in visited):
			continue
		visited.add(nij)
		dist[nij] = 1 + dist[vij]
		B.appendleft(nij)
print(max(dist))


from collections import deque
(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [(0, 1), (1, 0), (0, -1), (-1, 0)]
q = deque()
cnt = h * w
t = 0
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append((i, j))
			a[i][j] = 0
			cnt -= 1
while cnt:
	(y, x) = q.popleft()
	for (dx, dy) in d:
		if 0 <= x + dx < w and 0 <= y + dy < h and (a[y + dy][x + dx] == '.'):
			a[y + dy][x + dx] = a[y][x] + 1
			cnt -= 1
			q.append((y + dy, x + dx))
for i in range(h):
	m = max(a[i])
	t = max(t, m)
print(t)


(h, w) = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1:1] = (list('#' + input() + '#') for _ in range(h))
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = ((-1, 0), (1, 0), (0, -1), (0, 1))
r = -1
while p:
	r += 1
	s = []
	for (i, j) in p:
		for (di, dj) in d:
			di += i
			dj += j
			if a[di][dj] == '.':
				a[di][dj] = '#'
				s.append((di, dj))
	p = s
print(r)


from collections import deque
(H, W) = map(int, input().split())
B = [[-1] * W for _ in range(H)]
queue = deque([])
for i in range(H):
	A = input()
	for j in range(W):
		if A[j] == '#':
			B[i][j] = 0
			queue.append((i, j))
ans = 0
while queue:
	(I, J) = queue.popleft()
	for (di, dj) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
		(i, j) = (I + di, J + dj)
		if 0 <= i < H and 0 <= j < W:
			if B[i][j] < 0:
				B[i][j] = B[I][J] + 1
				ans = max(ans, B[i][j])
				queue.append((i, j))
print(ans)


from collections import deque
(H, W) = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
seen = [[False] * W for _ in range(H)]
ans = 0
dq = deque([])
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			dq.append((i, j, 0))
			seen[i][j] = True
while len(dq):
	(x, y, d) = dq.popleft()
	ans = max(ans, d)
	for (nx, ny) in [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]:
		if 0 <= nx < H and 0 <= ny < W:
			if not seen[nx][ny]:
				dq.append((nx, ny, d + 1))
				seen[nx][ny] = True
print(ans)


(h, w) = map(int, input().split())
a = [['#'] * (w + 2)] * 2
a[1:1] = (['#'] + list(input()) + ['#'] for _ in range(h))
d = ((-1, 0), (1, 0), (0, -1), (0, 1))
step = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']

def next_step():
	r = []
	for (i, j) in step:
		for (di, dj) in d:
			di += i
			dj += j
			if a[di][dj] == '.':
				a[di][dj] = '#'
				r.append((di, dj))
	return r
n = h * w - len(step)
r = 0
while n:
	r += 1
	step = next_step()
	n -= len(step)
print(r)


from collections import deque
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
visited = [[-1] * w for _ in range(h)]
queue = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			visited[i][j] = 0
			queue.append([i, j])
while queue:
	(y, x) = queue.popleft()
	for (j, k) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		(n_y, n_x) = (y + j, x + k)
		if 0 <= n_y < h and 0 <= n_x < w and (a[n_y][n_x] == '.') and (visited[n_y][n_x] < 0):
			visited[n_y][n_x] = visited[y][x] + 1
			queue.append([n_y, n_x])
ans = 0
for l in visited:
	ans = max([ans] + l)
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
q = deque()
for w in range(W):
	for h in range(H):
		if A[h][w] == '#':
			q.append((h, w, 0))
ans = 0
while q:
	(h, w, d) = q.popleft()
	ans = max(ans, d)
	for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
		(nh, nw) = (h + dh, w + dw)
		if nh < 0 or nh >= H or nw < 0 or (nw >= W):
			continue
		if A[nh][nw] == '#':
			continue
		A[nh][nw] = '#'
		q.append((nh, nw, d + 1))
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
	s = list(input())
	for (w, x) in zip(range(W), s):
		if x == '#':
			mat.append((h, w, 0))
	dp[h] = s
while len(mat):
	(h, w, cnt) = mat.popleft()
	for (t, h, w, cnt) in [(h > 0, h - 1, w, cnt), (h < H - 1, h + 1, w, cnt), (w > 0, h, w - 1, cnt), (w < W - 1, h, w + 1, cnt)]:
		if t and dp[h][w] == '.':
			mat.append((h, w, cnt + 1))
			dp[h][w] = '#'
print(cnt)


from collections import deque
(h, w) = map(int, input().split())
A = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
	for j in range(w):
		if A[i][j] == '#':
			que.append((i, j))
			dist[i][j] = 0
ans = 0
while que:
	(y, x) = que.popleft()
	for (dy, dx) in zip(di, dj):
		(ny, nx) = (y + dy, x + dx)
		if ny < 0 or ny >= h or nx < 0 or (nx >= w):
			continue
		if dist[ny][nx] != -1:
			continue
		dist[ny][nx] = dist[y][x] + 1
		ans = max(ans, dist[ny][nx])
		que.append((ny, nx))
print(ans)


(h, w) = map(int, input().split())
a = ''.join((input() + '#' for _ in range(h)))
a = a.replace('.', '1').replace('#', '0')
bits = int(a, 2)
w1 = w + 1
h1 = h + 1
bits <<= w1
frame = (1 << w1) - 1
frame |= frame << h1 * w1
frame |= sum((1 << b for b in range(w1, h1 * w1, w1)))
count = 0
while bits:
	count += 1
	mask = bits | frame
	bits &= mask << w1 & mask >> w1 & mask << 1 & mask >> 1
print(count)


from queue import deque

def main():
	(h, w) = map(int, input().split())
	grids = [False] * (w * h)
	dq = deque()
	for i in range(h):
		for (j, c) in enumerate(list(input().strip())):
			if c == '#':
				grids[i * w + j] = True
				dq.append((0, i, j))
	while dq:
		(cnt, i, j) = dq.popleft()
		for (dx, dy) in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
			if 0 <= i + dx < h and 0 <= j + dy < w and (not grids[(i + dx) * w + (j + dy)]):
				grids[(i + dx) * w + (j + dy)] = True
				dq.append((cnt + 1, i + dx, j + dy))
	print(cnt)
main()


from collections import deque
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
d = deque()
dist = [[-1] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			d.append([i, j])
			dist[i][j] = 0
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
while d:
	(x1, y1) = d.popleft()
	for i in range(4):
		x2 = x1 + dx[i]
		y2 = y1 + dy[i]
		if 0 <= x2 < h and 0 <= y2 < w and (dist[x2][y2] == -1):
			d.append([x2, y2])
			dist[x2][y2] = dist[x1][y1] + 1
print(max(list(map(lambda x: max(x), dist))))


(H, W) = map(int, input().split())
l = [list(input()) for _ in range(H)]
from collections import deque
q = deque()
for (i, r) in enumerate(l):
	for (j, c) in enumerate(r):
		if c == '#':
			l[i][j] = 0
			q.append((i, j))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while q:
	(y, x) = q.popleft()
	for (dy, dx) in d:
		if 0 <= y + dy < H and 0 <= x + dx < W and (l[y + dy][x + dx] == '.'):
			l[y + dy][x + dx] = l[y][x] + 1
			q.append((y + dy, x + dx))
m = 0
for r in l:
	for c in r:
		if m < c:
			m = c
print(m)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for i in range(H)]
Q = deque()
INF = H + W + 1
C = [[-1] * W for i in range(H)]
for y in range(H):
	for x in range(W):
		if A[y][x] == '#':
			Q.append((y, x))
			C[y][x] = 0
X = [1, 0, -1, 0]
Y = [0, -1, 0, 1]
while Q:
	(y, x) = Q.popleft()
	for i in range(4):
		ny = y + Y[i]
		nx = x + X[i]
		if 0 <= ny < H and 0 <= nx < W and (C[ny][nx] == -1) and (A[ny][nx] == '.'):
			C[ny][nx] = C[y][x] + 1
			Q.append((ny, nx))
ans = 0
for i in range(H):
	ans = max(ans, max(C[i]))
print(ans)


from collections import deque
(H, W) = map(int, input().split())
mp = [list(input()) for _ in range(H)]
ds = [[-1, 0], [1, 0], [0, -1], [0, 1]]
q = deque([])
cnt = 0
for i in range(H):
	for j in range(W):
		if mp[i][j] == '#':
			q.append((i, j, 0))
			cnt += 1
if cnt == H * W:
	print(0)
	exit()
while q:
	t = q.popleft()
	for d in ds:
		ny = t[0] + d[0]
		nx = t[1] + d[1]
		if 0 <= ny < H and 0 <= nx < W:
			if mp[ny][nx] == '.':
				mp[ny][nx] = '#'
				q.append((ny, nx, t[2] + 1))
				cnt += 1
				if cnt == H * W:
					print(t[2] + 1)
					exit()


from collections import deque
(h, w) = map(int, input().split())
mz = []
q = deque()
for i in range(h):
	mz.append(list(input()))
	ls = [[i, j, 0] for (j, a) in enumerate(mz[-1]) if a == '#']
	q.extend(ls)
delta = [[-1, 0], [0, -1], [1, 0], [0, 1]]
while q:
	(y, x, c) = q.popleft()
	for (dy, dx) in delta:
		if 0 <= y + dy < h and 0 <= x + dx < w:
			if mz[y + dy][x + dx] == '.':
				mz[y + dy][x + dx] = '#'
				q.append([y + dy, x + dx, c + 1])
			else:
				pass
print(c)


import sys
import math
from collections import deque
input = sys.stdin.readline
(h, w) = map(int, input().split())
a = [list(map(str, input())) for _ in range(h)]
b = deque()
n = [-1] * (h * w)
p = ((1, 0), (-1, 0), (0, 1), (0, -1))
for x in range(h):
	for y in range(w):
		if a[x][y] == '#':
			b.append((x, y))
			n[x * w + y] = 0
while b:
	(x, y) = b.popleft()
	for idx in p:
		(s, t) = idx
		if 0 <= x + s < h and 0 <= y + t < w:
			if n[(x + s) * w + (y + t)] == -1:
				n[(x + s) * w + (y + t)] = n[x * w + y] + 1
				b.append((x + s, y + t))
print(max(n))


from collections import deque
(H, W) = map(int, input().split())
que = deque()
A = [input() for i in range(H)]
dist = [[-1] * W for i in range(H)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			dist[i][j] = 0
			que.append((i, j))
d = 0
while que:
	(y, x) = que.popleft()
	d = dist[y][x]
	for (dx, dy) in dd:
		nx = x + dx
		ny = y + dy
		if not 0 <= nx < W or not 0 <= ny < H or dist[ny][nx] != -1:
			continue
		dist[ny][nx] = d + 1
		que.append((ny, nx))
print(d)


from collections import deque
(h, w) = map(int, input().split())
al = [input() for _ in range(h)]
inf = 10 ** 9
m = [[inf] * w for _ in range(h)]
q = deque([])
for hi in range(h):
	for wi in range(w):
		if al[hi][wi] == '#':
			m[hi][wi] = 0
			q.append((hi, wi))
while len(q) > 0:
	(ch, cw) = q.popleft()
	c = m[ch][cw]
	for (hi, wi) in [[ch + 1, cw], [ch, cw + 1], [ch - 1, cw], [ch, cw - 1]]:
		if h > hi >= 0 and w > wi >= 0 and (m[hi][wi] > c + 1):
			m[hi][wi] = c + 1
			q.append((hi, wi))
res = max([max(m[i]) for i in range(h)])
print(res)


(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = ((-1, 0), (1, 0), (0, -1), (0, 1))
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']

def f():
	s = []
	for (i, j) in p:
		for (di, dj) in d:
			di += i
			dj += j
			if 0 <= di < h and 0 <= dj < w and (a[di][dj] == '.'):
				a[di][dj] = '#'
				s.append((di, dj))
	return s
n = h * w - len(p)
r = 0
while n:
	r += 1
	p = f()
	n -= len(p)
print(r)


from collections import deque
(H, W) = map(int, input().split())
S = [input() for _ in range(H)]
paint = ((1, 0), (-1, 0), (0, 1), (0, -1))
que = deque([])
dark = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		if S[i][j] == '#':
			que.append((i, j, 0))
			dark[i][j] = 1
ans = 0
while len(que) > 0:
	(di, dj, c) = que.popleft()
	for (pi, pj) in paint:
		(ni, nj) = (pi + di, pj + dj)
		if 0 <= ni < H and 0 <= nj < W and (dark[ni][nj] == 0):
			dark[ni][nj] = 1
			que.append((ni, nj, c + 1))
			ans = c + 1
print(ans)


(h, w) = map(int, input().split())
a = [input() for i in range(h)]
b = [-1] * h * w
c = []
d = 0
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			b[i * w + j] = 0
			c.append(i * w + j)
while len(c) < h * w:
	if c[d] // w != 0:
		if b[c[d] - w] == -1:
			b[c[d] - w] = b[c[d]] + 1
			c.append(c[d] - w)
	if c[d] % w != 0:
		if b[c[d] - 1] == -1:
			b[c[d] - 1] = b[c[d]] + 1
			c.append(c[d] - 1)
	if c[d] % w != w - 1:
		if b[c[d] + 1] == -1:
			b[c[d] + 1] = b[c[d]] + 1
			c.append(c[d] + 1)
	if c[d] // w != h - 1:
		if b[c[d] + w] == -1:
			b[c[d] + w] = b[c[d]] + 1
			c.append(c[d] + w)
	d += 1
print(max(b))


from collections import deque
(h, w) = map(int, input().split())
a = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append((i, j))
ans = 0
while q:
	nq = deque()
	while True:
		(y, x) = q.popleft()
		for (dy, dx) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			ny = dy + y
			nx = dx + x
			if 0 <= ny < h and 0 <= nx < w and (a[ny][nx] != '#'):
				a[ny][nx] = '#'
				nq.append((ny, nx))
		if not q:
			ans += 1
			q = nq
			break
print(ans - 1)


from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
(h, w) = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if board[i][j] == '#':
			board[i][j] = True
			q.append((i, j, 0))
		else:
			board[i][j] = False
ans = 0
while q:
	(i, j, cnt) = q.popleft()
	for (x, y) in zip(dx, dy):
		if 0 <= i + x < h and 0 <= j + y < w and (not board[i + x][j + y]):
			board[i + x][j + y] = True
			q.append((i + x, j + y, cnt + 1))
			ans = max(ans, cnt + 1)
print(ans)


import queue
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
q = []
dist = [[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append([i, j])
			dist[i][j] = 0
q = queue.deque(q)
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while q:
	(y, x) = q.popleft()
	for (dy, dx) in d:
		(ny, nx) = (y + dy, x + dx)
		if 0 <= ny and ny < h and (0 <= nx) and (nx < w) and (dist[ny][nx] == -1):
			dist[ny][nx] = dist[y][x] + 1
			q.append([ny, nx])
ans = 0
for i in range(h):
	for j in range(w):
		ans = max(ans, dist[i][j])
print(ans)


from collections import deque
(h, w) = map(int, input().split())
a = ['#' * (w + 2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w + 2)]
for i in range(h + 2):
	a[i] = list(a[i])
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque([])
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if a[i][j] == '#':
			q.append((i, j, 0))
ans = 0
while q:
	(i, j, c) = q.popleft()
	for (di, dj) in d:
		if a[i + di][j + dj] == '.':
			a[i + di][j + dj] = '#'
			q.append((i + di, j + dj, c + 1))
	ans = max(ans, c)
print(ans)


from collections import deque

def main():
	(h, w) = map(int, input().split())
	mp = [input() for _ in range(h)]
	dist = [-1] * (h * w)
	q = deque()
	for i in range(h):
		for j in range(w):
			if mp[i][j] == '#':
				q.append(i * w + j)
				dist[i * w + j] = 0
			else:
				dist[i * w + j] = -1
	while q:
		c = q.popleft()
		x = c // w
		y = c % w
		for (i, j) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
			(xx, yy) = (x + i, y + j)
			if 0 <= xx < h and 0 <= yy < w and (dist[xx * w + yy] == -1):
				dist[xx * w + yy] = dist[x * w + y] + 1
				q.append(xx * w + yy)
	print(max(dist))
	return
main()


from collections import deque
(h, w) = map(int, input().split())
l = [list(input()) for i in range(h)]
dis = [[10000] * w for i in range(h)]
q = deque([])
for i in range(h):
	for j in range(w):
		if l[i][j] == '#':
			q.append([i, j, 0])
			dis[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while q:
	(x, y, d) = q.popleft()
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx < h and 0 <= ny < w and (dis[nx][ny] > d + 1):
			dis[nx][ny] = d + 1
			q.append([nx, ny, d + 1])
ans = 0
for i in dis:
	ans = max(ans, max(i))
print(ans)


from collections import deque
(H, W) = map(int, input().split())
C = []
Q = deque()
dist = [[-1] * W for i in range(H)]
for i in range(H):
	s = list(input())
	yxidx = [(i, x) for (x, v) in enumerate(s) if v == '#']
	for (y, x) in yxidx:
		Q.append((y, x))
		dist[y][x] = 0
	C.append(s)
X = [1, 0, -1, 0]
Y = [0, -1, 0, 1]
while Q:
	(y, x) = Q.popleft()
	for i in range(4):
		nx = x + X[i]
		ny = y + Y[i]
		if 0 <= nx < W and 0 <= ny < H and (dist[ny][nx] == -1):
			dist[ny][nx] = dist[y][x] + 1
			Q.append((ny, nx))
ans = 0
for i in range(H):
	ans = max(ans, max(dist[i]))
print(ans)


from collections import deque
(H, W) = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
	for w in range(W):
		if hw[h][w] == '#':
			b.append([h, w, 0])
ans = 0
while len(b) > 0:
	(h, w, d) = b.popleft()
	d += 1
	for (y, x) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		(nh, nw) = (h + y, w + x)
		if nh >= 0 and nh < H and (nw >= 0) and (nw < W) and (hw[nh][nw] == '.'):
			b.append([nh, nw, d])
			if ans < d:
				ans = d
			hw[nh][nw] = '#'
print(ans)


from collections import deque
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 10
dist = [[inf if c == '.' else 0 for c in r] for r in a]
dq = deque()
for i in range(h):
	for j in range(w):
		if dist[i][j] == 0:
			dq.append([i, j])
diff = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
while dq:
	(y, x) = dq.popleft()
	for (dy, dx) in diff:
		y2 = y + dy
		x2 = x + dx
		if 0 <= y2 < h and 0 <= x2 < w and (dist[y2][x2] > dist[y][x] + 1):
			dq.append([y2, x2])
			dist[y2][x2] = dist[y][x] + 1
			ans = max(ans, dist[y2][x2])
print(ans)


def main():
	from collections import deque
	(s, *c) = open(0)
	(h, w) = map(int, s.split())
	f = [-1] * h * w
	q = deque()
	for (i, c) in enumerate(''.join((t[:w] for t in c))):
		if c == '#':
			q.append(i)
			f[i] = 0
	while q:
		i = q.popleft()
		v = f[i] + 1
		(j, k, l, m, u) = (i + w, i - w, i + 1, i - 1, i % w)
		if h * w > j and f[j] < 0:
			q.append(j)
			f[j] = v
		if k >= 0 and f[k] < 0:
			q.append(k)
			f[k] = v
		if w > u + 1 and f[l] < 0:
			q.append(l)
			f[l] = v
		if u and f[m] < 0:
			q.append(m)
			f[m] = v
	print(v - 1)
main()


from collections import deque
(h, w) = [int(_) for _ in input().split()]
G = [list(input()) for _ in range(h)]
que = deque()
for i in range(h):
	for j in range(w):
		if G[i][j] == '#':
			que.append((i, j, 0))
cnt = 0
while que:
	(i, j, c) = que.popleft()
	for (ni, nj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		if i + ni < 0 or j + nj < 0:
			continue
		if i + ni >= h or j + nj >= w:
			continue
		if G[i + ni][j + nj] == '.':
			G[i + ni][j + nj] = '#'
			que.append((i + ni, j + nj, c + 1))
			cnt = max(cnt, c + 1)
print(cnt)


(h, w) = map(int, input().split())
s = set()
a = []
from collections import deque
q = deque([])
for i in range(h):
	tmp = list(input())
	a.append(tmp)
	for j in range(w):
		if tmp[j] == '#':
			q.append((i, j, 0))
ans = 0
ll = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while q:
	(x, y, v) = q.popleft()
	ans = max(ans, v)
	for (i, j) in ll:
		if 0 <= x + i < h and 0 <= y + j < w and (a[i + x][j + y] == '.'):
			a[i + x][j + y] = '#'
			q.append((i + x, j + y, v + 1))
print(ans)


(h, w) = map(int, input().split())
a = [list(input()) for i in range(h)]
from collections import deque
v = [[0] * w for i in range(h)]
m = [[-1, 0], [0, -1], [1, 0], [0, 1]]
que = deque([])
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			v[i][j] = 1
			que.append([i, j, 0])
while len(que) > 0:
	n = que.popleft()
	for i in m:
		(ni, nj) = (i[0] + n[0], i[1] + n[1])
		if ni >= 0 and nj >= 0 and (ni < h) and (nj < w):
			if v[ni][nj] == 0:
				v[ni][nj] = 1
				que.append([ni, nj, n[2] + 1])
print(n[2])


import collections
(H, W) = map(int, input().split())
went = [[False] * W for i in range(H)]
queue = collections.deque()
for hoge in range(H):
	for (huga, t) in enumerate(input()):
		if t == '#':
			went[hoge][huga] = True
			queue.append([hoge, huga, 0])
while queue:
	(curx, cury, ct) = queue.popleft()
	for (dx, dy) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		(newx, newy) = (curx + dx, cury + dy)
		newct = ct + 1
		if 0 <= newx < H and 0 <= newy < W and (not went[newx][newy]):
			went[newx][newy] = True
			queue.append([newx, newy, newct])
print(ct)


(H, W) = map(int, input().split())
A = []
q = []
for i in range(H):
	As = list(input())
	A.append(As)
	for j in range(W):
		if A[i][j] == '#':
			q.append((i, j))
r = 0
while q:
	q2 = []
	for (i, j) in q:
		if i - 1 >= 0 and A[i - 1][j] == '.':
			A[i - 1][j] = '#'
			q2.append((i - 1, j))
		if i + 1 < H and A[i + 1][j] == '.':
			A[i + 1][j] = '#'
			q2.append((i + 1, j))
		if j - 1 >= 0 and A[i][j - 1] == '.':
			A[i][j - 1] = '#'
			q2.append((i, j - 1))
		if j + 1 < W and A[i][j + 1] == '.':
			A[i][j + 1] = '#'
			q2.append((i, j + 1))
	q = q2
	r += 1
r -= 1
print(r)


from heapq import *
(h, w) = map(int, input().split())
grid = [['#'] * (w + 2)] + [list('#' + input() + '#') for x in range(h)] + [['#'] * (w + 2)]
stack = []
for y in range(1, h + 1):
	for x in range(1, w + 1):
		if grid[y][x] == '#':
			grid[y][x] = 0
			stack.append((y, x))
for i in range(h * w):
	tmp = []
	for (my, mx) in stack:
		for (y, x) in ([0, 1], [1, 0], [-1, 0], [0, -1]):
			if grid[my + y][mx + x] == '.':
				grid[my + y][mx + x] = i + 1
				tmp.append([my + y, mx + x])
	stack = tmp
	if len(tmp) == 0:
		print(i)
		break


from collections import deque
(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append((i, j, 0))
while q:
	(y, x, d) = q.popleft()
	if a[y][x] == '#':
		for (xdx, ydy) in zip((x, x, x + 1, x - 1), (y + 1, y - 1, y, y)):
			if 0 <= xdx < w and 0 <= ydy < h:
				if a[ydy][xdx] == '.':
					a[ydy][xdx] = '#'
					q.append((ydy, xdx, d + 1))
print(d)


from collections import deque
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
move = ((1, 0), (0, 1), (-1, 0), (0, -1))
que = deque([])
visited = [[0] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			que.append((i, j, 0))
			visited[i][j] = 1
while len(que) > 0:
	(ci, cj, d) = que.popleft()
	for (mi, mj) in move:
		(ni, nj) = (mi + ci, mj + cj)
		if 0 <= ni < h and 0 <= nj < w and (visited[ni][nj] == 0):
			if a[ni][nj] == '.':
				visited[ni][nj] = 1
				que.append((ni, nj, d + 1))
print(d)


from collections import deque
(H, W) = map(int, input().split())
m = [[-1 if c == '.' else 0 for c in input() + '#'] for _ in range(H)]
m.append([0] * (W + 1))
todo = deque(((h, w) for h in range(H) for w in range(W) if m[h][w] == 0))
ans = 0
while todo:
	(h, w) = todo.popleft()
	count = m[h][w] + 1
	for (dh, dw) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		nh = h + dh
		nw = w + dw
		if m[nh][nw] == -1:
			m[nh][nw] = count
			todo.append((nh, nw))
			ans = count
print(ans)


from collections import deque
(H, W) = map(int, input().split())
coords = []
blacks = deque([])
for i in range(H):
	rows = list(input())
	coords.append(rows)
	for (j, row) in enumerate(rows):
		if row == '#':
			blacks.append((i, j, 0))
ans = 0
while len(blacks) > 0:
	(h, w, dist) = blacks.popleft()
	ans = max(dist, ans)
	for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
		ni = h + di
		nj = w + dj
		if 0 <= ni < H and 0 <= nj < W:
			if coords[ni][nj] == '.':
				blacks.append((ni, nj, dist + 1))
				coords[ni][nj] = '#'
print(ans)


from collections import deque
(H, W) = map(int, input().split())
field = []
dist = [[-1] * W for _ in range(H)]
que = deque()
for i in range(H):
	tmp = list(input())
	for j in range(W):
		if tmp[j] == '#':
			dist[i][j] = 0
			que.append([i, j])
	field.append(tmp)
DX = [1, 0, -1, 0]
DY = [0, 1, 0, -1]
ans = 0
while que:
	(y, x) = map(int, que.popleft())
	ans = dist[y][x]
	for (dx, dy) in zip(DX, DY):
		nx = x + dx
		ny = y + dy
		if nx < 0 or nx >= W or ny < 0 or (ny >= H):
			continue
		if dist[ny][nx] == -1:
			dist[ny][nx] = dist[y][x] + 1
			que.append([ny, nx])
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [input() for _ in range(H)]
q = deque([])
grid = [[-1] * W for _ in range(H)]
dire = ((1, 0), (0, 1), (-1, 0), (0, -1))
d = 0
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			q.append((i, j))
			grid[i][j] = 0
while q:
	(i, j) = q.popleft()
	d = grid[i][j]
	for (dy, dx) in dire:
		(ny, nx) = (i + dy, j + dx)
		if ny >= 0 and ny < H and (nx >= 0) and (nx < W) and (grid[ny][nx] < 0):
			q.append((ny, nx))
			grid[ny][nx] = grid[i][j] + 1
print(d)


from collections import deque
(H, W) = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]
Q = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			Q.append((i, j, 0))
ma = 0
while Q:
	(i, j, dist) = Q.popleft()
	ma = max(ma, dist)
	for (ni, nj) in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
		if 0 <= ni < H and 0 <= nj < W and (A[ni][nj] == '.'):
			A[ni][nj] = '#'
			Q.append((ni, nj, dist + 1))
print(ma)


from collections import deque
(h, w) = map(int, input().split())
c = []
d = [[-1 for i in range(w)] for j in range(h)]
q = deque()
for i in range(h):
	s = input()
	c.append(s)
	for j in range(w):
		if c[i][j] == '#':
			q.append([i, j, 0])
			d[i][j] = 0
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q) != 0:
	(y, x, z) = q[0]
	for i in range(4):
		(ny, nx) = (y + dirr[i][0], x + dirr[i][1])
		if 0 <= ny < h and 0 <= nx < w and (d[ny][nx] == -1) and (c[ny][nx] != '#'):
			q.append([ny, nx, z + 1])
			d[ny][nx] = z + 1
	q.popleft()
print(z)


from collections import *
(h, w) = map(int, input().split())
c = eval('list(input()),' * h)
q = deque()
for i in range(h):
	for j in range(w):
		if c[i][j] == '#':
			q.append((i, j, 0))
ans = 0
while q:
	(y, x, v) = q.popleft()
	ans = max(ans, v)
	for (i, j) in ((y, x - 1), (y, x + 1), (y - 1, x), (y + 1, x)):
		if h > i >= 0 and w > j >= 0 and (c[i][j] == '.'):
			c[i][j] = '#'
			q.append((i, j, v + 1))
print(ans)


from collections import deque

def clamp(a, b, c):
	return min(max(a, b), c)
(H, W) = map(int, input().split())
A = [input() for _ in range(H)]
D = [[-1] * W for _ in range(H)]
dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
Q = deque()
res = 0
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			D[i][j] = 0
			Q.append([i, j, 0])
while len(Q) > 0:
	(x, y, n) = Q.popleft()
	for (dx, dy) in dd:
		xx = clamp(x + dx, 0, H - 1)
		yy = clamp(y + dy, 0, W - 1)
		if D[xx][yy] == -1:
			D[xx][yy] = n + 1
			Q.append([xx, yy, n + 1])
			res = n + 1
print(res)


(H, W) = map(int, input().split())
maze = [list(input()) for _ in range(H)]
blacks = []
for i in range(H):
	for j in range(W):
		if maze[i][j] == '#':
			blacks.append((i, j))
count = 0
while len(blacks) != 0:
	count += 1
	nexts = []
	for (x, y) in blacks:
		for (nx, ny) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
			if 0 <= nx < H and 0 <= ny < W and (maze[nx][ny] == '.'):
				maze[nx][ny] = '#'
				nexts.append((nx, ny))
	blacks = nexts
print(count - 1)


from collections import deque
(h, w) = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[-1] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
q = deque()
for i in range(h):
	for j in range(w):
		if grid[i][j] == '#':
			q.append((i, j))
			cost[i][j] = 0
while q:
	(x, y) = q.popleft()
	for (dx, dy) in nb:
		nx = x + dx
		ny = y + dy
		if 0 <= nx and nx < h and (0 <= ny) and (ny < w) and (cost[nx][ny] == -1):
			cost[nx][ny] = cost[x][y] + 1
			q.append((nx, ny))
print(max([max(c) for c in cost]))


import sys
input = sys.stdin.readline
(h, w) = map(int, input().split())
A = [[False] * (w + 2) for _ in range(h + 2)]
(chk, chk2) = ([], [])
for i in range(h):
	s = input()
	for j in range(w):
		A[i + 1][j + 1] = s[j] == '.'
		if s[j] == '#':
			chk.append((i + 1, j + 1))
ans = 0
d = ((1, 0), (0, 1), (-1, 0), (0, -1))
while chk:
	for (cx, cy) in chk:
		for (dx, dy) in d:
			if A[cx + dx][cy + dy] == True:
				chk2.append((cx + dx, cy + dy))
				A[cx + dx][cy + dy] = False
	if chk2:
		ans += 1
	chk = chk2
	chk2 = []
print(ans)


(h, w) = map(int, input().split())
grid = [[-1] * w for _ in range(h)]
from collections import deque
que = deque()
for i in range(h):
	s = list(input())
	for j in range(w):
		if s[j] == '#':
			grid[i][j] = 0
			que.append((i, j))
dirc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while que:
	kuro = que.popleft()
	n = grid[kuro[0]][kuro[1]]
	for (dx, dy) in dirc:
		x = kuro[0] + dx
		y = kuro[1] + dy
		if 0 <= x < h and 0 <= y < w and (grid[x][y] == -1):
			grid[x][y] = n + 1
			que.append((x, y))
ans = 0
for i in range(h):
	ans = max(ans, max(grid[i]))
print(ans)


(h, w) = map(int, input().split())
a = list((list(input()) for i in range(h)))
stack = []
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			stack.append((i, j))
vec = ((1, 0), (0, 1), (-1, 0), (0, -1))
move = 0
while stack:
	next = []
	move += 1
	for (y, x) in stack:
		for (ny, nx) in vec:
			(ty, tx) = (y + ny, x + nx)
			if ty > h - 1 or tx > w - 1 or ty < 0 or (tx < 0):
				continue
			if a[ty][tx] == '.':
				a[ty][tx] = move
				next.append((ty, tx))
	stack = next
print(move - 1)


from collections import deque
(h, w) = map(int, input().split())
A = [list(input()) for _ in range(h)]
V = [[-1] * w for _ in range(h)]
que = deque([])
for (i, a) in enumerate(A):
	for (j, _a) in enumerate(a):
		if _a == '#':
			que.append([i, j])
			V[i][j] = 0
dhdw = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while que:
	(nwh, nww) = que.popleft()
	for (dh, dw) in dhdw:
		if not (0 <= nwh + dh < h and 0 <= nww + dw < w):
			continue
		if V[nwh + dh][nww + dw] != -1:
			continue
		V[nwh + dh][nww + dw] = V[nwh][nww] + 1
		que.append([nwh + dh, nww + dw])
print(max(map(max, V)))


(h, w) = map(int, input().split())
a = [input() for i in range(h)]
from collections import deque
q = deque()
reach = [[False] * w for i in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append([i, j, 0])
			reach[i][j] = True
ans = 0
while q:
	(i, j, cnt) = q.popleft()
	ans = max(ans, cnt)
	for (k, l) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		if 0 <= i + k < h and 0 <= j + l < w:
			if not reach[i + k][j + l]:
				q.append([i + k, j + l, cnt + 1])
				reach[i + k][j + l] = True
print(ans)


from collections import deque
(H, W) = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()
for h in range(H):
	for w in range(W):
		if m[h][w] == '#':
			q.append((h, w, 0))
while q:
	(h, w, c) = q.popleft()
	ans = max(ans, c)
	for (dh, dw) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
		if 0 <= h + dh < H and 0 <= w + dw < W and (m[h + dh][w + dw] == '.'):
			m[h + dh][w + dw] = '#'
			q.append((h + dh, w + dw, c + 1))
print(ans)


from collections import deque
(h, w) = map(int, input().split())
a = []
for _ in range(h):
	a.append(list(input()))
q = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append((i, j, 0))
dxdy = [(-1, 0), (0, -1), (0, 1), (1, 0)]
ans = 0
while q:
	(y, x, cnt) = q.popleft()
	for (dx, dy) in dxdy:
		if not (0 <= x + dx < w and 0 <= y + dy < h):
			continue
		if a[y + dy][x + dx] == '.':
			a[y + dy][x + dx] = '#'
			q.append((y + dy, x + dx, cnt + 1))
			ans = cnt + 1
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [input() for i in range(H)]
dxy = [(0, 1), (1, 0), (0, -1), (-1, 0)]
INF = 99999
dp = [[INF] * W for i in range(H)]
q = deque()
for (y, row) in enumerate(A):
	for (x, c) in enumerate(row):
		if c == '#':
			dp[y][x] = 0
			q.append((x, y))
while q:
	(x, y) = q.popleft()
	d = dp[y][x]
	for (dx, dy) in dxy:
		(nx, ny) = (x + dx, y + dy)
		if not 0 <= nx < W:
			continue
		if not 0 <= ny < H:
			continue
		if dp[ny][nx] <= d + 1:
			continue
		dp[ny][nx] = d + 1
		q.append((nx, ny))
print(max((max(row) for row in dp)))


(H, W) = map(int, input().split())
HW = [[-1 for w in range(W)] for h in range(H)]
from collections import deque
Q = deque()
for h in range(H):
	S = input()
	for w in range(W):
		if S[w] == '#':
			Q.append([h, w])
			HW[h][w] = 0
X = [0, 0, -1, 1]
Y = [-1, 1, 0, 0]
ans = 0
while Q:
	(h, w) = Q.popleft()
	for i in range(len(X)):
		(ih, iw) = (h + Y[i], w + X[i])
		if not (0 <= ih < H and 0 <= iw < W):
			continue
		if HW[ih][iw] >= 0:
			continue
		HW[ih][iw] = HW[h][w] + 1
		ans = max(ans, HW[ih][iw])
		Q.append([ih, iw])
print(ans)


import copy
from collections import deque
(H, W) = map(int, input().split())
A = [[-1] * W for _ in range(H)]
d = deque()
for h in range(H):
	s = input()
	for w in range(W):
		if s[w] == '.':
			pass
		else:
			A[h][w] = 0
			d.append((h, w))
DIF = [(1, 0), (0, 1), (-1, 0), (0, -1)]
while d:
	point = d.popleft()
	for dif in DIF:
		x = point[0] + dif[0]
		y = point[1] + dif[1]
		if 0 <= x < H and 0 <= y < W and (A[x][y] == -1):
			d.append((x, y))
			A[x][y] = A[point[0]][point[1]] + 1
ans = 0
for h in range(H):
	Amax = max(A[h])
	ans = max(ans, Amax)
print(ans)


from collections import deque
INF = 10 ** 18
(h, w) = map(int, input().split())
e = [input() for _ in range(h)]
d = [[INF] * w for _ in range(h)]
q = deque([])
for i in range(h):
	for j in range(w):
		if e[i][j] == '#':
			q.append((i, j))
			d[i][j] = 0
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
ans = 0
while q:
	(x, y) = q.popleft()
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx < h and 0 <= ny < w and (e[nx][ny] == '.') and (d[nx][ny] == INF):
			q.append((nx, ny))
			d[nx][ny] = d[x][y] + 1
			ans = max(d[nx][ny], ans)
print(ans)


(H, W) = map(int, input().split())
B = [list(input()) for i in range(H)]
l = []
for i in range(H):
	for j in range(W):
		if B[i][j] == '#':
			l.append((i, j))

def a(l):
	n = []
	d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	for (y, x) in l:
		for (dy, dx) in d:
			ny = y + dy
			nx = x + dx
			if 0 <= ny < H and 0 <= nx < W and (B[ny][nx] == '.'):
				B[ny][nx] = '#'
				n.append((ny, nx))
	return set(n)
ans = 0
while len(l) != 0:
	l = a(l)
	ans += 1
print(ans - 1)


from collections import deque

def main():
	(h, w) = map(int, input().split())
	(ans, q) = (0, deque())
	visited = [[0 if j == '#' else -1 for j in input()] for _ in range(h)]
	q = deque([(i, j) for i in range(h) for j in range(w) if visited[i][j] == 0])
	while q:
		(x, y) = q.popleft()
		for (i, j) in ((0, 1), (1, 0), (-1, 0), (0, -1)):
			(newx, newy) = (x + i, y + j)
			if 0 <= newx < h and 0 <= newy < w:
				if visited[newx][newy] == -1:
					visited[newx][newy] = visited[x][y] + 1
					q.append((newx, newy))
					ans = max(ans, visited[newx][newy])
	return print(ans)
main()


from collections import deque
(h, w) = map(int, input().split())
a = []
d = []
que = deque()
for i in range(h):
	a.append(list(input()))
	d.append([1e+100] * w)
	for j in range(w):
		if a[i][j] == '#':
			que.append([i, j])
			d[i][j] = 0
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]
ans = 0
while que:
	(i, j) = que.popleft()
	for k in range(4):
		ni = i + di[k]
		nj = j + dj[k]
		if 0 <= ni < h and 0 <= nj < w and (d[ni][nj] == 1e+100):
			d[ni][nj] = d[i][j] + 1
			ans = max(ans, d[ni][nj])
			que.append([ni, nj])
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
blacks = deque([])
for h in range(H):
	for w in range(W):
		if A[h][w] == '#':
			blacks.append((h, w))
count = 0
while len(blacks) > 0:
	newblacks = deque([])
	while len(blacks) > 0:
		b = blacks.popleft()
		for (y, x) in zip((b[0] - 1, b[0], b[0], b[0] + 1), (b[1], b[1] - 1, b[1] + 1, b[1])):
			if y < 0 or y >= H or x < 0 or (x >= W):
				continue
			if A[y][x] == '.':
				newblacks.append((y, x))
			A[y][x] = '#'
	blacks = newblacks
	count += 1
print(count - 1)


from collections import deque
(h, w) = map(int, input().split())
p = [list('#' * (w + 2))] + [list('#' + input() + '#') for i in range(h)] + [list('#' * (w + 2))]
q = deque([])
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if p[i][j] == '#':
			p[i][j] = 0
			q.append([i, j])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
	(x, y) = q.popleft()
	for (dx, dy) in d:
		if p[x + dx][y + dy] == '.':
			p[x + dx][y + dy] = p[x][y] + 1
			q.append([x + dx, y + dy])
ans = 0
for i in range(1, h + 1):
	for j in range(1, w + 1):
		ans = max(ans, p[i][j])
print(ans)


from collections import deque
(h, w) = map(int, input().split())
grid = [list(input()) for _ in range(h)]
nxt = deque()
for i in range(h):
	for j in range(w):
		if grid[i][j] == '#':
			nxt.append((i, j, 0))
a = 0
while nxt:
	(i, j, t) = nxt.popleft()
	if t > a:
		a += 1
	for (i, j) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
		if (-1 < i < h) & (-1 < j < w) and grid[i][j] == '.':
			grid[i][j] = '#'
			nxt.append((i, j, t + 1))
print(a)


from collections import deque
(H, W) = map(int, input().split())
q = deque()
A = []
for h in range(H):
	r = input()
	for w in range(W):
		if r[w] == '#':
			q.append([h, w])
	A.append([0 if s == '#' else -1 for s in r])
d = [[-1, 0], [0, -1], [0, 1], [1, 0]]
p = 0
while q:
	(h, w) = q.popleft()
	p = A[h][w] + 1
	for (dh, dw) in d:
		nh = h + dh
		nw = w + dw
		if not 0 <= nh < H:
			continue
		if not 0 <= nw < W:
			continue
		if A[nh][nw] == -1:
			A[nh][nw] = p
			q.append([nh, nw])
print(p - 1)


from collections import deque
(h, w) = map(int, input().split())
maze = [list(input()) for i in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
Q = deque()
for i in range(h):
	for j in range(w):
		if maze[i][j] == '#':
			Q.append((i, j, 0))
while Q:
	(x, y, z) = Q.popleft()
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx < h and 0 <= ny < w and (maze[nx][ny] == '.'):
			Q.append((nx, ny, z + 1))
			maze[nx][ny] = '#'
print(z)


from collections import deque
(H, W) = map(int, input().split())
field = []
spos = deque([])
for i in range(H):
	s = list(input())
	for j in range(W):
		if s[j] == '#':
			spos.append((j, i))
	field.append(s)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ans = -1
while spos:
	for _ in range(len(spos)):
		(x, y) = spos.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or nx >= W or ny < 0 or (ny >= H):
				pass
			elif field[ny][nx] == '.':
				field[ny][nx] = '#'
				spos.append((nx, ny))
	ans += 1
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [input() for i in range(H)]
X = [1, 0, -1, 0]
Y = [0, -1, 0, 1]
INF = 99999
dp = [[-1] * W for i in range(H)]
q = deque()
for (y, row) in enumerate(A):
	for (x, c) in enumerate(row):
		if c == '#':
			dp[y][x] = 0
			q.append((y, x))
while q:
	(y, x) = q.popleft()
	d = dp[y][x]
	for i in range(4):
		nx = x + X[i]
		ny = y + Y[i]
		if 0 <= nx < W and 0 <= ny < H and (dp[ny][nx] == -1):
			dp[ny][nx] = d + 1
			q.append((ny, nx))
ans = 0
for i in dp:
	ans = max(ans, max(i))
print(ans)


import collections
(h, w) = map(int, input().split())
cells = []
for i in range(h):
	row = input()
	cells.append([c == '#' for c in row])
blacks = collections.deque()
for i in range(h):
	for j in range(w):
		if cells[i][j]:
			blacks.append((i, j, 0))
res = 0
while blacks:
	(y, x, c) = blacks.popleft()
	for (dy, dx) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
		if 0 <= y + dy < h and 0 <= x + dx < w and (not cells[y + dy][x + dx]):
			cells[y + dy][x + dx] = True
			blacks.append((y + dy, x + dx, c + 1))
			res = c + 1
print(c)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
p = deque()
for (i, Ai) in enumerate(A):
	for (j, Aij) in enumerate(Ai):
		if Aij == '#':
			p.append([i, j, 0])
while p:
	(y, x, cnt) = p.popleft()
	for (dx, dy) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		if 0 <= y + dy < H and 0 <= x + dx < W and (A[y + dy][x + dx] == '.'):
			p.append([y + dy, x + dx, cnt + 1])
			A[y + dy][x + dx] = '#'
print(cnt)


(H, W) = map(int, input().split())
field = [list(input()) for _ in range(H)]
state = []
for h in range(H):
	for w in range(W):
		if field[h][w] == '#':
			state.append([w, h])
tmp = []
ret = 0
while len(state) > 0:
	tmp = list()
	ret += 1
	for (x, y) in state:
		for (nx, ny) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
			nx += x
			ny += y
			if nx < 0 or ny < 0 or nx >= W or (ny >= H):
				continue
			if field[ny][nx] == '.':
				field[ny][nx] = '#'
				tmp.append([nx, ny])
	state = tmp
print(ret - 1)


from collections import deque
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
memo = [[-1 if j == '.' else 0 for j in list(i)] for i in a]
q = []
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append([i, j])
q = deque(q)
while q:
	(x, y) = q.popleft()
	for (s, t) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		if 0 <= x + s and 0 <= y + t and (x + s < h) and (y + t < w):
			if memo[x + s][y + t] < 0:
				memo[x + s][y + t] = memo[x][y] + 1
				q.append([x + s, y + t])
print(max((max(i) for i in memo)))


import sys
input = sys.stdin.readline
from collections import deque
(h, w) = map(int, input().split())
MAP = [list(input().strip()) for _ in range(h)]
q = deque()
for (i, M) in enumerate(MAP):
	for (j, m) in enumerate(M):
		if m == '#':
			q.append((i, j, 0))
delta = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
while q:
	(x, y, d) = q.popleft()
	ans = max(ans, d)
	for (dx, dy) in delta:
		if 0 <= x + dx < h and 0 <= y + dy < w:
			if MAP[x + dx][y + dy] == '.':
				MAP[x + dx][y + dy] = '#'
				q.append((x + dx, y + dy, d + 1))
print(ans)


from collections import deque
(h, w) = map(int, input().split())
l = []
l.append('@' * (w + 2))
for i in range(h):
	l.append('@' + input() + '@')
l.append('@' * (w + 2))
q = deque()
p = [[-1 for i in j] for j in l]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if l[i][j] == '#':
			q.append([i, j])
			p[i][j] = 0
while len(q) > 0:
	(x, y) = q.popleft()
	for (i, j) in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
		if l[x + i][y + j] == '.' and p[x + i][y + j] == -1:
			q.append([x + i, y + j])
			p[x + i][y + j] = p[x][y] + 1
a = 0
for i in p:
	for j in i:
		a = max(a, j)
print(a)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
sharps = []
for (h, line) in enumerate(A):
	sharps += [[h, w, 0] for (w, p) in enumerate(line) if p == '#']
q = deque(sharps)
while q:
	(i, j, score) = q.popleft()
	for (mi, mj) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
		ni = i + mi
		nj = j + mj
		if ni < 0 or H <= ni or nj < 0 or (W <= nj) or (A[ni][nj] == '#'):
			continue
		A[ni][nj] = '#'
		q.append([ni, nj, score + 1])
print(score)


from collections import deque
(h, w) = map(int, input().split())
maze = [list(input()) for i in range(h)]
d = [[-1] * w for i in range(h)]
que = deque([])
dd = ((1, 0), (0, 1), (-1, 0), (0, -1))
for i in range(h):
	for j in range(w):
		if maze[i][j] == '#':
			que.append((i, j))
			d[i][j] = 0
ans = 0
while que:
	p = que.popleft()
	ans = d[p[0]][p[1]]
	for (dx, dy) in dd:
		nx = p[0] + dx
		ny = p[1] + dy
		if 0 <= nx and nx < h and (0 <= ny) and (ny < w) and (maze[nx][ny] != '#') and (d[nx][ny] == -1):
			d[nx][ny] = ans + 1
			que.append((nx, ny))
print(ans)


from collections import deque
(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
q = deque([])
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append([i, j])
			q.append(0)
while q:
	(y, x) = q.popleft()
	ans = q.popleft() + 1
	for (dy, dx) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		(ny, nx) = (dy + y, dx + x)
		if ny < 0 or nx < 0 or ny >= h or (nx >= w):
			continue
		if a[ny][nx] == '.':
			a[ny][nx] = '#'
			q.append([ny, nx])
			q.append(ans)
print(ans - 1)


from collections import deque
(h, w) = map(int, input().split())
d = deque()
op = [[-1] * w for i in range(h)]
for i in range(h):
	s = input().rstrip()
	for j in range(len(s)):
		if s[j] == '#':
			d.append((i, j, 0))
			op[i][j] = 0
while d:
	(i, j, step) = d.popleft()
	for (i2, j2) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
		if 0 <= i2 < h and 0 <= j2 < w:
			if op[i2][j2] == -1:
				d.append((i2, j2, step + 1))
				op[i2][j2] = step + 1
print(max([max(op[i]) for i in range(h)]))


from collections import deque
(h, w) = map(int, input().split())
m = [input() for _ in range(h)]
vm = [[-1] * w for _ in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if m[i][j] == '#':
			q.append((i, j))
			vm[i][j] = 0
while q:
	(y, x) = q.popleft()
	d = vm[y][x]
	for (i, j) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
		(yi, xj) = (y + i, x + j)
		if yi >= 0 and xj >= 0 and (yi < h) and (xj < w) and (vm[yi][xj] == -1):
			vm[yi][xj] = d + 1
			q.append([yi, xj])
print(d)


from collections import deque
(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
dxy = [(0, 1), (1, 0), (-1, 0), (0, -1)]
inf = float('inf')
dp = [[inf] * w for _ in range(h)]
q = deque()
for (y, l) in enumerate(a):
	for (x, c) in enumerate(l):
		if c == '#':
			dp[y][x] = 0
			q.append((x, y))
ans = 0
while q:
	(x, y) = q.popleft()
	d = dp[y][x]
	for (dx, dy) in dxy:
		(nx, ny) = (x + dx, y + dy)
		if not 0 <= nx < w:
			continue
		if not 0 <= ny < h:
			continue
		if dp[ny][nx] <= d + 1:
			continue
		dp[ny][nx] = d + 1
		q.append((nx, ny))
		ans = max(ans, d + 1)
print(ans)


from collections import deque
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
(H, W) = map(int, input().split())
MAP = []
for _ in range(H):
	MAP.append(list(input()))
d = deque()
for i in range(H):
	for j in range(W):
		if MAP[i][j] == '#':
			d.append([i, j, 0])
ans = 0
while len(d) != 0:
	(x, y, cnt) = d.popleft()
	for i in range(4):
		nx = x + tx[i]
		ny = y + ty[i]
		if 0 <= nx < H and 0 <= ny < W and (MAP[nx][ny] == '.'):
			MAP[nx][ny] = '#'
			d.append([nx, ny, cnt + 1])
			ans = max(ans, cnt + 1)
print(ans)


import collections
(h, w) = map(int, input().split())
area = []
q = collections.deque()
for i in range(h):
	area.append(list(input()))
	ls = [(i, j, 0) for j in range(w) if area[-1][j] == '#']
	q.extend(ls)
d = [[-1, 0], [0, -1], [1, 0], [0, 1]]
co = 0
while q:
	(y, x, c) = q.popleft()
	for (dy, dx) in d:
		if 0 <= y + dy < h and 0 <= x + dx < w:
			if area[y + dy][x + dx] == '.':
				area[y + dy][x + dx] = '#'
				co = max(c + 1, co)
				q.append((y + dy, x + dx, c + 1))
print(co)


(h, w) = map(int, input().split())
n = []
a = []
a.append(['&'] * (w + 2))
for i in range(h):
	arrc = list(input())
	arrc = ['&'] + arrc + ['&']
	b = arrc
	for j in range(len(arrc)):
		if b[j] == '#':
			n.append((i + 1, j))
	a.append(b)
a.append(['&'] * (w + 2))
p = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = -1
while n:
	cnt += 1
	n2 = []
	for (i, j) in n:
		for (di, dj) in p:
			di += i
			dj += j
			if a[di][dj] == '.':
				a[di][dj] = '#'
				n2.append((di, dj))
	n = n2
print(cnt)


(h, w) = map(int, input().split())
a = ['*' * (w + 2)] + ['*' + input() + '*' for _ in range(h)] + ['*' * (w + 2)]
from collections import deque
d = deque()
c = [[0] * w for _ in range(h)]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		if a[i][j] == '#':
			d.append([i, j])
di = [[0, 1], [1, 0], [-1, 0], [0, -1]]
while d:
	g = d.popleft()
	for i in di:
		x = g[0] + i[0]
		y = g[1] + i[1]
		if a[x][y] == '.':
			if c[x - 1][y - 1] == 0:
				d.append([x, y])
				c[x - 1][y - 1] = c[g[0] - 1][g[1] - 1] + 1
m = 0
for i in range(h):
	for j in range(w):
		m = max(m, c[i][j])
print(m)


from collections import deque
(a, b) = map(int, input().split())
List = []
q = deque([[0, 0]])
for i in range(a):
	l = list(input())
	for _ in range(b):
		if l[_] == '#':
			q.append([i, _])
			l[_] = 0
	List.append(l)
q.popleft()
aaa = [[0, 1], [0, -1], [1, 0], [-1, 0]]
ans = 0
while q:
	(h, w) = q.popleft()
	for (x, y) in aaa:
		if 0 <= h + x < a and 0 <= w + y < b:
			if List[h + x][w + y] == '.':
				List[h + x][w + y] = List[h][w] + 1
				q.append([h + x, w + y])
				if List[h + x][w + y] > ans:
					ans = List[h + x][w + y]
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [input() for i in range(H)]
Map = [[-1] * W for i in range(H)]
d = deque([])
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			Map[i][j] = 0
			d.append([i, j])
ans = 0
while d:
	(x, y) = d.popleft()
	dist = Map[x][y]
	for (dx, dy) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
		(u, v) = (x + dx, y + dy)
		if 0 <= u < H and 0 <= v < W and (Map[u][v] == -1):
			Map[u][v] = dist + 1
			ans = max(ans, dist + 1)
			d.append([u, v])
print(ans)


(h, w) = map(int, input().split())
al = [list(input()) for _ in range(h)]
cnt = 0
q = []
for hi in range(h):
	for wi in range(w):
		if al[hi][wi] == '#':
			q.append((hi, wi))
while len(q) > 0:
	nq = []
	cnt += 1
	for (hi, wi) in q:
		for d in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
			if h > hi + d[0] >= 0 and w > wi + d[1] >= 0:
				if al[hi + d[0]][wi + d[1]] == '.':
					al[hi + d[0]][wi + d[1]] = '#'
					nq.append((hi + d[0], wi + d[1]))
	q = nq
print(cnt - 1)


(h, w) = map(int, input().split())
G = [input() for _ in range(h)]
from collections import deque
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
que = deque([])
for i in range(h):
	for j in range(w):
		if G[i][j] == '#':
			que.append((i, j, 0))
c = 0
visit = [[0] * w for _ in range(h)]
while len(que) > 0:
	(ni, nj, c) = que.popleft()
	for (di, dj) in move:
		(mi, mj) = (ni + di, nj + dj)
		if 0 <= mi < h and 0 <= mj < w and (G[mi][mj] == '.') and (visit[mi][mj] == 0):
			visit[mi][mj] = 1
			que.append((mi, mj, c + 1))
print(c)


from collections import deque
(h, w) = map(int, input().split())
m = [list(input()) for _ in range(h)]
flag = [[True] * w for _ in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if m[i][j] == '#':
			q.appendleft((i, j, 0))
			flag[i][j] = False
ans = 0
while q:
	(i, j, n) = q.pop()
	ans = n
	for (dx, dy) in zip([1, 0, -1, 0], [0, 1, 0, -1]):
		ni = i + dx
		nj = j + dy
		if 0 <= ni < h and 0 <= nj < w and flag[ni][nj]:
			flag[ni][nj] = False
			q.appendleft((ni, nj, n + 1))
print(ans)


(h, w) = map(int, input().split())
a = []
for i in range(h):
	a.append([it == '#' for it in input()])
q = []
for i in range(h):
	for j in range(w):
		if a[i][j]:
			q.append((i, j))
cnt = -1
while q:
	cnt += 1
	r = []
	for (i, j) in q:
		if i > 0 and (not a[i - 1][j]):
			a[i - 1][j] = True
			r += [(i - 1, j)]
		if i < h - 1 and (not a[i + 1][j]):
			a[i + 1][j] = True
			r += [(i + 1, j)]
		ai = a[i]
		if j > 0 and (not ai[j - 1]):
			ai[j - 1] = True
			r += [(i, j - 1)]
		if j < w - 1 and (not ai[j + 1]):
			ai[j + 1] = True
			r += [(i, j + 1)]
	q = r
print(cnt)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for _ in range(H)]
q = []
for y in range(H):
	for x in range(W):
		if A[y][x] == '#':
			q.append((y, x))
ret = 0
while True:
	r = []
	while q:
		(cy, cx) = q.pop()
		for (dy, dx) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
			(ny, nx) = (cy + dy, cx + dx)
			if 0 <= ny < H and 0 <= nx < W and (A[ny][nx] == '.'):
				A[ny][nx] = '#'
				r.append((ny, nx))
	ret += 1
	if len(r) == 0:
		break
	q = r
print(ret - 1)


from collections import deque

def mbfs(S, H, W):
	dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
	while len(d) != 0:
		(h, w, x) = d.popleft()
		for (t, y) in dxy:
			if 0 <= h + t <= H - 1 and 0 <= w + y <= W - 1 and (S[h + t][w + y] != '#'):
				S[h + t][w + y] = '#'
				d.append([h + t, w + y, x + 1])
	return x
(H, W) = map(int, input().split())
A = [list(input()) for i in range(H)]
d = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			d.append([i, j, 0])
print(mbfs(A, H, W))


from collections import deque
(h, w) = map(int, input().split())
grid = [input() for i in range(h)]
dist = [[-1] * w for _ in range(h)]
p = deque()
d = 0
for i in range(h):
	for j in range(w):
		if grid[i][j] == '#':
			p.append((i, j))
			dist[i][j] = 0
while p:
	(y, x) = p.popleft()
	d = dist[y][x]
	for (dy, dx) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
		if 0 <= x + dx < w and 0 <= y + dy < h and (dist[y + dy][x + dx] == -1):
			dist[y + dy][x + dx] = d + 1
			p.append((y + dy, x + dx))
print(d)


from collections import deque
import sys
input = sys.stdin.readline
(h, w) = map(int, input().split())
a = [list(input().rstrip()) for i in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			a[i][j] = 0
			q.append((i, j, 0))
		else:
			a[i][j] = -1
while q:
	(s, t, cnt) = q.popleft()
	for (ns, nt) in ((s + 1, t), (s - 1, t), (s, t + 1), (s, t - 1)):
		if 0 <= ns <= h - 1 and 0 <= nt <= w - 1 and (a[ns][nt] == -1):
			q.append((ns, nt, cnt + 1))
			a[ns][nt] = cnt + 1
ans = 0
for i in range(h):
	for j in range(w):
		ans = max(ans, a[i][j])
print(ans)


from collections import deque
(H, W) = map(int, input().split())
A = [list(input()) for i in range(H)]
q = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			q.append((i, j))
			dist[i][j] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
while len(q) > 0:
	(x, y) = q.popleft()
	for k in range(4):
		nx = x + dx[k]
		ny = y + dy[k]
		if not (0 <= nx < H and 0 <= ny < W):
			continue
		if dist[nx][ny] == -1:
			dist[nx][ny] = dist[x][y] + 1
			q.append((nx, ny))
print(max([max(i) for i in dist]))


(H, W) = map(int, input().split())
masu = []
for i in range(H):
	masu.append(list(input()))
black = []
for i in range(H):
	for j in range(W):
		if masu[i][j] == '#':
			black.append([i, j])
ans = -1
while len(black) != 0:
	ans += 1
	blacktemp = black[:]
	black = []
	for k in blacktemp:
		for (i, j) in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
			if 0 <= k[0] + i <= H - 1 and 0 <= k[1] + j <= W - 1:
				if masu[k[0] + i][k[1] + j] == '.':
					masu[k[0] + i][k[1] + j] = '#'
					black.append([k[0] + i, k[1] + j])
print(ans)


from collections import deque
(H, W) = map(int, input().split())
d = []
for i in range(H):
	d.append([0 if c == '#' else -1 for c in input()])
q = deque()
for i in range(H):
	for j in range(W):
		if not d[i][j]:
			q.append((i, j))
while q:
	u = q.popleft()
	(ui, uj) = u
	for v in [(ui - 1, uj), (ui + 1, uj), (ui, uj - 1), (ui, uj + 1)]:
		(vi, vj) = v
		if 0 <= vi <= H - 1 and 0 <= vj <= W - 1 and (d[vi][vj] == -1):
			d[vi][vj] = d[ui][uj] + 1
			q.append(v)
print(max((max(di) for di in d)))


from collections import deque
(h, w) = map(int, input().split())
graph = []
finished = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1, -1]
x = [1, -1, 0, 0]
q = deque([])
for i in range(h):
	a = input()
	graph.append(a)
	for j in range(w):
		if a[j] == '#':
			q.append((i, j, 0))
while q:
	c = q.popleft()
	for i in range(4):
		nh = c[0] + y[i]
		nw = c[1] + x[i]
		if nh < 0 or nh >= h or nw < 0 or (nw >= w) or (graph[nh][nw] == '#') or finished[nh][nw]:
			continue
		finished[nh][nw] = True
		q.append((nh, nw, c[2] + 1))
print(c[2])


from collections import deque
dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
(H, W) = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()
for i in range(H):
	field.append(['#'] + list(input()) + ['#'])
	for j in range(W):
		if field[i + 1][j + 1] == '#':
			q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0
while q:
	(y, x, lv) = q.popleft()
	res = max(lv, res)
	for (dy, dx) in dyx:
		if field[y + dy][x + dx] == '.':
			field[y + dy][x + dx] = '#'
			q.append((y + dy, x + dx, lv + 1))
print(res)


(H, W) = map(int, input().split())
A = [list(input()) for i in range(H)]
que = []
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			que.append((i, j))
			A[i][j] = 1
		else:
			A[i][j] = 0
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
count = 0
while que:
	h = []
	for (x, y) in que:
		for (dx, dy) in d:
			(nx, ny) = (x + dx, y + dy)
			if 0 <= nx < H and 0 <= ny < W and (A[nx][ny] == 0):
				A[nx][ny] = 1
				h.append((nx, ny))
	que = h
	count += 1
print(count - 1)


from collections import deque
(h, w) = map(int, input().split())
alist = [input().strip() for i in range(h)]
dxy = [(0, 1), (1, 0), (0, -1), (-1, 0)]
INF = 99999
dp = [[INF] * w for i in range(h)]
q = deque()
for (y, row) in enumerate(alist):
	for (x, c) in enumerate(row):
		if c == '#':
			dp[y][x] = 0
			q.append((x, y))
while q:
	(x, y) = q.popleft()
	d = dp[y][x]
	for (dx, dy) in dxy:
		(nx, ny) = (x + dx, y + dy)
		if not 0 <= nx < w:
			continue
		if not 0 <= ny < h:
			continue
		if dp[ny][nx] <= d + 1:
			continue
		dp[ny][nx] = d + 1
		q.append((nx, ny))
print(max((max(row) for row in dp)))


from collections import deque
(H, W) = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			q.append((i, j))
			c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
	(y, x) = q.popleft()
	for (dy, dx) in D:
		(ny, nx) = (y + dy, x + dx)
		if 0 <= ny < H and 0 <= nx < W and (c[ny][nx] == -1):
			q.append((ny, nx))
			c[ny][nx] = c[y][x] + 1
print(max([max(l) for l in c]))


from collections import deque
(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [[-1] * w for _ in range(h)]
que = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			que.append((j, i))
			d[i][j] = 0
dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
while que:
	(x, y) = que.popleft()
	for (dx, dy) in dxdy:
		nx = x + dx
		ny = y + dy
		if 0 <= nx < w and 0 <= ny < h and (d[ny][nx] == -1):
			que.append((nx, ny))
			d[ny][nx] = d[y][x] + 1
			ans = max(ans, d[ny][nx])
print(ans)


INF = float('inf')

def main():
	(H, W) = map(int, input().split())
	A = [input() for _ in range(H)]
	D = [[0 if A[h][w] == '#' else INF for w in range(W)] for h in range(H)]
	for h in range(H):
		for w in range(1, W):
			D[h][w] = min(D[h][w], D[h][w - 1] + 1)
		for w in range(W - 2, -1, -1):
			D[h][w] = min(D[h][w], D[h][w + 1] + 1)
	for w in range(W):
		for h in range(1, H):
			D[h][w] = min(D[h][w], D[h - 1][w] + 1)
		for h in range(H - 2, -1, -1):
			D[h][w] = min(D[h][w], D[h + 1][w] + 1)
	print(max((d for dd in D for d in dd)))
main()


import itertools
from collections import deque
(H, W) = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
Q = deque([])
for (i, j) in itertools.product(range(H), range(W)):
	if A[i][j] == '#':
		Q += [[i, j, 0]]
while Q:
	(i, j, d) = Q.popleft()
	for (ni, nj) in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < H and 0 <= nj < W and (A[ni][nj] == '.'):
			A[ni][nj] = '#'
			Q += [[ni, nj, d + 1]]
print(d)


from collections import deque
(h, w) = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2)] + [[0] + [inf] * w + [0] for _ in range(h)] + [[0] * (w + 2)]
d = deque()
for i in range(h):
	for (j, k) in enumerate(input()):
		if k == '#':
			a[i + 1][j + 1] = 0
			d.append((i + 1, j + 1))
stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0
while d:
	(x, y) = d.popleft()
	for (k, l) in stp:
		(nx, ny) = (x + k, y + l)
		if a[x][y] + 1 < a[nx][ny]:
			a[nx][ny] = a[x][y] + 1
			res = max(res, a[nx][ny])
			d.append((nx, ny))
print(res)


from collections import deque
(h, w) = list(map(int, input().split()))
a = [[c for c in input()] for _ in range(h)]
visit = [[0] * w for _ in range(h)]
q = deque()
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			deque.appendleft(q, (i, j, 0))
			visit[i][j] = 1
ans = 0
while len(q) > 0:
	(i, j, cnt) = deque.pop(q)
	ans = max(ans, cnt)
	for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
		ni = i + di
		nj = j + dj
		if 0 <= ni < h and 0 <= nj < w and (visit[ni][nj] == 0):
			visit[ni][nj] = 1
			deque.appendleft(q, (ni, nj, cnt + 1))
print(ans)


from collections import deque
(H, W) = map(int, input().split())
INF = 10 ** 9
sheet = []
log = [[True] * W for i in range(H)]
step = [(-1, 0), (1, 0), (0, -1), (0, 1)]
stuck = deque()
ans = 0
for i in range(H):
	line = input()
	for j in range(W):
		if line[j] == '#':
			stuck += [(i, j, 0)]
			log[i][j] = False
while stuck:
	(y, x, m) = stuck.popleft()
	for s in step:
		(dx, dy) = s
		if x + dx < 0 or x + dx > W - 1 or y + dy < 0 or (y + dy > H - 1):
			continue
		if log[y + dy][x + dx]:
			log[y + dy][x + dx] = False
			stuck += [(y + dy, x + dx, m + 1)]
			if ans < m + 1:
				ans = m + 1
print(ans)


(h, w) = map(int, input().split())
a = [input() for _ in range(h)]
visited = [[0] * w for _ in range(h)]
from collections import deque
q = deque([])
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			q.append((i, j, 0))
			visited[i][j] = 1
ans = 0
while q:
	(i, j, count) = q.popleft()
	ans = max(ans, count)
	for (nxi, nxj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
		if 0 <= nxi < h and 0 <= nxj < w and (visited[nxi][nxj] == 0):
			visited[nxi][nxj] = 1
			q.append((nxi, nxj, count + 1))
print(ans)