Problem:
 Score : 300 points    Problem Statement 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.        Sample Input 1 3 3
...
.#.
...      Sample Output 1 2  After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.       Sample Input 2 6 6
..#..#
......
#..#..
......
.#....
....#.      Sample Output 2 3

Solution (Python):
from collections import deque

H, W = map(int, input().split())
A_arr = []
que = deque()
dist = [[-1 for i in range(W)] for i in range(H)]

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "
            que.append([i,j])
            dist[i][j] = 0

n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while 1:
    if len(que) == 0:
        break
    
    x, y = que.popleft()
    d = dist[x][y]
    for n in range(4):
        tmp = [x + n_list[n][0], y + n_list[n][1]]
        if tmp[0] < 0 or tmp[0] >= H:
            pass
        elif tmp[1] < 0 or tmp[1] >= W:
            pass
        elif dist[tmp[0]][tmp[1]] != -1:
            pass
        else:
            dist[tmp[0]][tmp[1]] = d + 1
            que.append([tmp[0], tmp[1]])


print(d)

Solution (Python):
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)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
m = ["
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[float("inf") for _ in range(W+2)] for _ in range(H+2)]

for h in range(1, H+1):
	for w in range(1, W+1):
		if m[h][w] == "
			q.appendleft([h, w])
			step[h][w] = 0

while q:
	label = q.pop()

	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if m[h][w] != "
			q.appendleft([h, w])
			step[h][w] = step[label[0]][label[1]] + 1

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		ans = max(ans, step[h][w])
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
A_array = [input() for i in range(H)]
adjusted_array = ((0, 1), (-1, 0), (0, -1), (1, 0))

distance = [[-1] * W for i in range(H)]

que = deque()

for i in range(H):
    for j in range(W):
        if A_array[i][j] == "
            distance[i][j] = 0
            que.append((i, j))


while (que):
    i, j = que.popleft()
    for adjusted in adjusted_array:
        x = j + adjusted[1]
        y = i + adjusted[0]
        if x >= W or x < 0 or y >= H or y < 0 or distance[y][x] != -1:
            continue
        distance[y][x] = distance[i][j] + 1
        que.append((y, x))

print(max([max(distance[i]) for i in range(H)]))

Solution (Python):
from collections import deque

H, W = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]

Q = deque((i, j, 0) for i in range(H) for j in range(W) if A[i][j] == "

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "
            Q.append((ni, nj, dist + 1))

print(ans)

Solution (Python):
from collections import deque

H, W = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]

Q = deque([(i, j, 0) for i in range(H) for j in range(W) if A[i][j] == "

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "
            Q.append((ni, nj, dist + 1))

print(ans)

Solution (Python):
import scipy.ndimage
import numpy as np

h,w = map(int, raw_input().split())

data = []

for a in range(h):
  q = raw_input()
  q = q.replace(".","1").replace("
  data.append( map(int,list(q)) )

A = np.array(data)
x = scipy.ndimage.morphology.distance_transform_cdt(A, metric='taxicab')

print np.max(x)

Solution (Python):
def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()

Solution (Python):
from collections import deque

H,W = map(int, input().split())
que = deque()
A = [input() for i in range(H)]

dy = [0,1,0,-1]
dx = [1,0,-1,0]
Field = [[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            Field[i][j] = 0
            que.append((i, j))

d = 0
while que:
    y,x = que.popleft()
    d = Field[y][x]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if not 0 <= nx < W or not 0 <= ny < H or Field[ny][nx] != -1:
            continue
        Field[ny][nx] = d+1
        que.append((ny, nx))
print(d)

Solution (Python):
import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa[i]
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)

Solution (Python):
import sys


def input():
    return sys.stdin.readline()[:-1]


H, W = map(int, input().split())

A = [[1 if s == "

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = []
[dist.extend(l[1:-1]) for l in lu[1:-1]]
print(max(dist))

Solution (Python):
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))

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "
            Q.append((ni, nj, dist + 1))

print(ans)

Solution (Python):


H, W = map(int, input().split())

m = []
l = []
end = 0
for y in range(H):
    h = list(input())
    m.append(h)
    for x, w in enumerate(h):
        if w == '
            l.append([y, x])
            end += 1
HW = H * W
ans = 0

while (end < HW):
    nl = []
    for ll in l:
        if (0 < ll[1]):
            if (m[ll[0]][ll[1] - 1] == '.'):
                m[ll[0]][ll[1] - 1] = '
                end += 1
                nl.append([ll[0], ll[1] - 1])

        if (ll[1] < W - 1):
            if (m[ll[0]][ll[1] + 1] == '.'):
                m[ll[0]][ll[1] + 1] = '
                end += 1
                nl.append([ll[0], ll[1] + 1])

        if (0 < ll[0]):
            if (m[ll[0] - 1][ll[1]] == '.'):
                m[ll[0] - 1][ll[1]] = '
                end += 1
                nl.append([ll[0] - 1, ll[1]])

        if (ll[0] < H - 1):
            if (m[ll[0] + 1][ll[1]] == '.'):
                m[ll[0] + 1][ll[1]] = '
                end += 1
                nl.append([ll[0] + 1, ll[1]])

    l = nl
    ans += 1

print(ans)

Solution (Python):
def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()

Solution (Python):
from collections import deque

H, W = map(int, input().split())


black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "
            black_cells.append(h * W + w)



def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p - W)
    if h != H-1:
        q_list.append(p + W)
    if w != 0:
        q_list.append(p - 1)
    if w != W-1:
        q_list.append(p + 1)
    return q_list


queue = deque(black_cells)
d = [10000] * (H * W)
for i in black_cells:
    d[i] = 0


while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Solution (Python):
from collections import deque

H,W = map(int,input().split())
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]

def bfs(l):
    ans = 0
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    ans = max(ans,check[ny][nx])
                    q.append([ny,nx])
    return ans 

L = []
for h,a in enumerate(A):
    for w,a_ in enumerate(a):
        if a_ == '
            L.append([h,w])
print(bfs(L))

Solution (Python):
from collections import deque
H,W = map(int, input().split())

cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
st = deque()
sts = deque()
push, pop = st.append, st.pop
pushs, pops = sts.append, sts.pop
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        
        if ai[w-1] == '
            cnt[h][w] = c
            push([h,w])
            fin += 1
        else:
            cnt[h][w] = -1


dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    while st:
        [h,w] = pop()
        for dx,dy in dxy:
            if cnt[h+dx][w+dy] == -1:
                
                cnt[h+dx][w+dy] = c+1
                pushs([h+dx,w+dy])
                fin += 1
    c += 1
    while sts:
        [h,w] = pops()
        push([h,w])


print(c)

Solution (Python):
h,w= map(int, input().split())
a = []
x = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '
            x.append((i, j))
    a.append(aa)
ans = 0
while True:
    xx = []
    for p in x:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if a[ppp[0]][ppp[1]] == '.':
                    a[ppp[0]][ppp[1]] = '
                    xx.append((ppp[0], ppp[1]))
    x = xx
    if len(x) == 0:
        break
    ans += 1
    
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
maze = [input()for _ in range(H)]


def bfs(queue: deque, reached: set) -> int:
    ans = 0
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while queue:
        d = queue.pop()
        if ans < d[2]:
            ans = d[2]
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if 0 <= x < W and 0 <= y < H and not reached[y][x]:
                queue.appendleft((x, y, d[2] + 1))
                reached[y][x] = True
    return ans


queue = deque()
reached = [[False for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            queue.append((j, i, 0))
            reached[i][j] = True
print(bfs(queue, reached))

Solution (Python):
INF = 10 ** 11
BLACK = '
H, W = [int(i) for i in input().split()]
M = [None] * H
D = [[INF] * W for _ in range(H)]

for i in range(H):
    inputs = input()
    for idx, j in enumerate(inputs):
        if j == BLACK:
            D[i][idx] = 0


def forward_update(i, j):
    up = INF
    if i > 0:
        up = D[i-1][j]
    left = INF
    if j > 0:
        left = D[i][j-1]

    D[i][j] = min(D[i][j], up + 1, left + 1)


def backward_update(i, j):
    down = INF
    if i < H-1:
        down = D[i+1][j]
    right = INF
    if j < W-1:
        right = D[i][j+1]
    D[i][j] = min(D[i][j], down + 1, right + 1)


_ = [forward_update(i, j) for i in range(H) for j in range(W)]
_ = [backward_update(i, j) for i in range(H-1, -1, -1) for j in range(W-1, -1, -1)]

max_value = max([max(x) for x in D])
print(max_value)

Solution (Python):
from collections import deque
def main():
    h, w = map(int, raw_input().split())
    s = [raw_input().strip() for _ in xrange(h)]
    q = deque()
    po = q.popleft
    pu = q.append
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '
                pu((i, j))
                a[i*w+j] = 0
    while q:
        x, y = po()
        z = a[x*w+y] + 1
        if x and a[(x-1)*w+y] > z:
            a[(x-1)*w+y] = z
            pu((x-1,y))
        if x < h - 1 and a[(x+1)*w+y] > z:
            a[(x+1)*w+y] = z
            pu((x+1,y))
        if y and a[x*w+y-1] > z:
            a[x*w+y-1] = z
            pu((x,y-1))
        if y < w - 1 and a[x*w+y+1] > z:
            a[x*w+y+1] = z
            pu((x,y+1))
    print z - 1
main()

Solution (Python):
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '

mat = [[True]*H for i in [0]*W]
for x,y in bk:
	mat[x][y] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1][y]:
			mat[x-1][y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1][y]:
			new.append((x+1,y))
			mat[x+1][y] = False
		if y > 0 and mat[x][y-1]:
			new.append((x,y-1))
			mat[x][y-1] = False
		if y < H-1 and mat[x][y+1]:
			new.append((x,y+1))
			mat[x][y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)

Solution (Python):
from scipy import ndimage
import numpy as np
import sys
input = sys.stdin.readline

H, W = map(int, input().split())

A_array = np.array(
    [[0 if s == "




b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Solution (Python):
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)

Solution (Python):
from heapq import*
h,w=map(int,input().split())
grid=[["

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

Solution (Python):
h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
ans=0
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="
            a[i][j]=0
            
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i in range(h):
    for j in range(w):
        k=a[-1-i][-1-j]+1
        if i!=h-1:
            if k<a[-i-2][-j-1]:
                a[-i-2][-j-1]=k

        if j!=w-1:        
            if k<a[-i-1][-j-2]:
                a[-i-1][-j-2]=k

for i in range(h):
    ans=max(ans,max(a[i]))
print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    h,w = LI()
    a = [sys.stdin.readline() for i in range(h)]
    s = 0
    p = deque()
    M = w*h
    d = [[-1 for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j] == "
                p.append((i,j))
                d[i][j] = 0
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    while p:
        y,x = p.popleft()
        for dy,dx in move:
            y2 = y+dy
            x2 = x+dx
            if 0 <= y2 < h and 0 <= x2 < w:
                if d[y2][x2] < 0:
                    d[y2][x2] = d[y][x]+1
                    p.append([y2,x2])
    ans = 0
    for i in d:
        for j in i:
            if j > ans:
                ans = j
    print(ans)
    return


def B():
    h,w,n = LI()
    sy,sx = LI()
    sy -= 1
    sx -= 1
    s = S()
    t = S()
    ks = list("LRUD")
    kt = list("RLDU")
    ds = [[0,-1],[0,1],[-1,0],[1,0]]
    dt = [[0,1],[0,-1],[1,0],[-1,0]]
    for i in range(4):
        y,x = [sy,sx]
        for j in range(n):
            if s[j] == ks[i]:
                y+=ds[i][0]
                x+=ds[i][1]
                if y < 0 or y >= h or x < 0 or x >= w:
                    print("NO")
                    quit()
            if t[j] == kt[i]:
                y += dt[i][0]
                x += dt[i][1]
                if y < 0:y = 0
                elif y >= h:y = h-1
                elif x < 0:x=0
                elif x >= w:x=w-1
    print("YES")
    return


def C():
    def dijkstra(s):
        d = [float("inf") for i in range(n)]
        d[s] = 0
        q=[[0,s]]
        while q:
            dx,x = heappop(q)
            for y in v[x]:
                if dx+1 < d[y]:
                    d[y] = dx+1
                    heappush(q,[d[y],y])
        return d
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = dijkstra(0)
    l = d.index(max(d))
    d = dijkstra(l)
    m = max(d)+1
    if m%3 == 2:
        print("Second")
    else:
        print("First")
    return


def D():
    n = I()
    return


def E():
    n = I()
    return


def F():
    n = I()
    return


if __name__ == "__main__":
    A()

Solution (Python):
H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)

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

Solution (Python):
H, W = map(int, input().split())

data = [[-W]*W for i in range(H)]

for i in range(H):
    s = input()
    x = -(2*W)
    for j in range(W):
        if s[j] == '
            x = 0
        data[i][j] = x
        x += 1
    x = -(2*W)
    for j in range(W):
        if data[i][W-j-1] == 0:
            x = 0
        elif data[i][W-j-1] < 0:
            data[i][W-j-1] = x
        else:
            if x > 0:
                x = min(x, data[i][W-j-1])
            else:
                x = data[i][W-j-1]
            data[i][W-j-1] = x
        x += 1


for w in range(W):
    x = -(2*H)
    for h in range(H):
        if data[h][w] == 0:
            x = 0
        elif data[h][w] > 0:
            if x > 0:
                x = min(x, data[h][w])
            else:
                x = data[h][w]
            data[h][w] = x
        else:
            data[h][w] = x
        x += 1
    x = -(2*H)
    for h in range(H):
        if data[H-h-1][w] == 0:
            x = 0
        elif data[H-h-1][w] > 0:
            if x > 0:
                x = min(x, data[H-h-1][w])
            else:
                x = data[H-h-1][w]
            data[H-h-1][w] = x
        else:
            data[H-h-1][w] = x
        x += 1

ans = 0
for d in data:
    ans = max(ans, max(d))
print(ans)

Solution (Python):
H,W = map(int,input().split())
A = [list(input()) for _ in range(H)]
B = [[0 for w in range(W+2)] for h in range(H+2)]
for h in range(1,H+1):
    for w in range(1,W+1):
        if A[h-1][w-1] == '
            B[h][w] = -1
for h in range(1,H+1):
    for w in range(1,W+1):
        if A[h-1][w-1] != '
            if B[h-1][w] == -1 or B[h+1][w] == -1 or B[h][w-1] == -1 or B[h][w+1] == -1:
                B[h][w] = 1
            else:
                if B[h-1][w] == 0 and B[h+1][w] == 0 and B[h][w-1] == 0 and B[h][w+1] == 0:
                    pass
                else:
                    k = [B[h-1][w],B[h+1][w],B[h][w-1],B[h][w+1]]
                    k = [i for i in k if i > 0]
                    B[h][w] = min(k)+1
for w in reversed(range(1,W+1)):
    for h in reversed(range(1,H+1)):
        if A[h-1][w-1] != '
            if B[h-1][w] == -1 or B[h+1][w] == -1 or B[h][w-1] == -1 or B[h][w+1] == -1:
                B[h][w] = 1
            else:
                if B[h-1][w] == 0 and B[h+1][w] == 0 and B[h][w-1] == 0 and B[h][w+1] == 0:
                    pass
                else:
                    k = [B[h-1][w],B[h+1][w],B[h][w-1],B[h][w+1]]
                    k = [i for i in k if i > 0]
                    B[h][w] = min(k)+1


ans = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        ans = max(ans,B[h][w])
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())


black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "
            black_cells.append(h * W + w)



def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p-W)
    if h != H-1:
        q_list.append(p+W)
    if w != 0:
        q_list.append(p-1)
    if w != W-1:
        q_list.append(p+1)
    return q_list


queue = deque(black_cells)
d = [10000]*(H*W)
for i in black_cells:
    d[i] = 0


while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Solution (Python):


import collections

h,w = [int(i) for i in input().split()]
board = [input() for j in range(h)] 

d4 = [[1,0],[0,1],[-1,0],[0,-1]]
memo = [[-1]*w for j in range(h)]
dist = [[100000]*w for j in range(h)]


q = collections.deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "
            memo[i][j] = 1
            q.append((i,j,0))

while len(q) != 0:

    i,j,c = q.popleft()
    dist[i][j] = c
    for k in d4:

        ii,jj = k
        if  i+ii < 0 or i+ii>=h or j+jj <0 or j+jj>=w:

            continue
        if memo[i+ii][j+jj] < 0:

            q.append((i+ii,j+jj,c+1))
            memo[i+ii][j+jj] = 1

ans = 0      
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])

print(ans)

Solution (Python):


import numpy


def main():
  height, width = map(int, input().split())
  max_value = height + width
  values = []

  for y in range(height):
    values.append([0 if v == '

  values = numpy.array(values)

  for x in range(width - 1):
    values[:, x + 1] = numpy.minimum(values[:, x] + 1, values[:, x + 1])

  for x in range(width - 1, 0, -1):
    values[:, x - 1] = numpy.minimum(values[:, x] + 1, values[:, x - 1])

  for y in range(height - 1):
    values[y + 1, :] = numpy.minimum(values[y, :] + 1, values[y + 1, :])

  for y in range(height - 1, 0, -1):
    values[y - 1, :] = numpy.minimum(values[y, :] + 1, values[y - 1, :])

  print(numpy.max(values), flush=True)


if __name__ == '__main__':
  main()

Solution (Python):
r,c = map(int,input().split())
grid = []
temp = []
limit = r*c
total = 0
count = 0
for i in range(r):
    next = list(input())
    for j in range(c):
        if next[j]=='
            temp.append([i,j])
            total+=1
    grid.append(next)
while(total<limit):
    nextround = []
    while(len(temp)>0):
        x,y = temp.pop()
        
        if x-1>-1:
            if grid[x-1][y] == '.':
                grid[x - 1][y] = '
                total +=1
                nextround.append([x-1,y])
        if x+1<r:

            if grid[x+1][y] == '.':
                grid[x + 1][y] = '
                total +=1
                nextround.append([x+1, y])
        if y-1>-1:
            if grid[x][y-1] == '.':
                grid[x][y-1] = '
                total +=1
                nextround.append([x,y-1])
        if y+1<c:
            if grid[x][y+1] == '.':
                grid[x][y+1] = '
                total +=1
                nextround.append([x,y+1])
    temp = nextround
    count+=1
print(count)

Solution (Python):

import sys
from collections import deque
INF = float("inf")


def solve(H: int, W: int, A: "List[str]"):
    
    black = []
    B = [[-1]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "
                black.append((i, j, 0))
                B[i][j] = 0

    q = deque()
    q.extend(black)

    while len(q) > 0:
        cy, cx, dis = q.popleft()
        for y, x in zip([cy-1, cy, cy+1, cy], [cx, cx-1, cx, cx+1]):
            if 0 <= y < H and 0 <= x < W and B[y][x] < 0:
                B[y][x] = dis+1
                q.append((y, x, dis+1))

    m = -INF
    for i in range(H):
        a = max(B[i])
        if m < a:
            m = a
    print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    A = [next(tokens) for _ in range(H)]  
    solve(H, W, A)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
H, W = list(map(int, input().split()))
A = [input() for _ in range(H)]
b = "
w = "."

wc = 0
L = []
wb = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if A[i][j] == w:
      wc += 1
    else:
      L.append([i, j])
      wb[i][j] = 1

Ans = 0
while wc > 0:
  L2 = []
  Ans += 1
  for ki, kj in L:
    if ki - 1 >= 0:
      if wb[ki - 1][kj] == 0:
        wb[ki - 1][kj] = 1
        wc -= 1
        L2.append([ki - 1 , kj])
    if ki + 1 < H:
      if wb[ki + 1][kj] == 0:
        wb[ki + 1][kj] = 1
        wc -= 1
        L2.append([ki + 1 , kj])
    if kj - 1 >= 0:
      if wb[ki][kj - 1] == 0:
        wb[ki][kj - 1] = 1
        wc -= 1
        L2.append([ki, kj - 1])
    if kj + 1 < W:
      if wb[ki][kj + 1] == 0:
        wb[ki][kj + 1] = 1
        wc -= 1
        L2.append([ki, kj + 1])
  L = L2
print(Ans)