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
import sys;input=sys.stdin.readline

h,w=map(int,input().split())
grid=[["

stack=deque()
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=deque()
    while stack:
        my,mx=stack.pop()
        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 not tmp:
        print(i)
        break

Solution (Python):
from collections import deque
import sys;input=sys.stdin.readline

h,w=map(int,input().split())
grid=[["

stack=deque()
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=deque()
    while stack:
        my,mx=stack.pop()
        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 not tmp:
        print(i)
        break

Solution (Python):
from collections import*
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
grid=[["

stack=deque()
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=deque()
    while stack:
        my,mx=stack.pop()
        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 not tmp:
        print(i)
        break

Solution (Python):
from collections import*
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
grid=[["

stack=deque()
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=deque()
    while stack:
        my,mx=stack.pop()
        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 not tmp:
        print(i)
        break

Solution (Python):
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))

queue = []
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
 
max_value = 0
while(True):
  if len(queue) == 0:
    break
  
  new_queue = []
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
print(max_value)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]

mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))

queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))












 


max_value = 0
while(True):
  
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  


print(max_value)

Solution (Python):
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
total = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '
            black.append([i,j])
            total += 1
    grid.append([line[j] for j in range(W)])

if H == 1 and W == 1:
    print(0)
else:
    if total == H*W:
        print(0)
        exit()
    while white:
        for coord in black:
            y = coord[0]
            x = coord[1]
            if y > 0:
                if grid[y-1][x] == '.':
                    grid[y-1][x] = '
                    nextb.append([y-1, x])
                    total += 1
            if y <= H-2:
                if grid[y+1][x] == '.':
                    grid[y+1][x] = '
                    nextb.append([y+1, x])
                    total += 1
            if x > 0:
                if grid[y][x-1] == '.':
                    grid[y][x-1] = '
                    nextb.append([y, x-1])
                    total += 1
            if x <= W-2:
                if grid[y][x+1] == '.':
                    grid[y][x+1] = '
                    nextb.append([y, x+1])
                    total += 1
        black = nextb
        nextb = []
        count += 1
        if total == H*W:
            white = False
        
    print(count)

Solution (Python):


import sys
import datetime
today = datetime.datetime.today

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def main_lte():
    H, W = i2nn()
    A = ii2ss(H)
    A = [[True] * (W + 2)] + [[True] + [s == '
    q = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == True:
                q.append((i, j))
    rec = 0
    while len(q) > 0:
        q2 = []
        for i0, j0 in q:
            i, j = i0 - 1, j0
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0 + 1, j0
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0, j0 - 1
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0, j0 + 1
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

import numpy as np
from scipy import ndimage

def main_scipy():
    H, W = i2nn()
    A = ii2ss(H)
    A = [[0 if s == '
    B = ndimage.morphology.distance_transform_cdt(A, metric='taxicab')
    n = np.max(B)
    print(n)

def main():
    main_scipy()

main()

Solution (Python):
import math
import time
import pprint
import sys
from collections import deque
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    
    require = [[0 for i in range(w)] for j in range(h)]
    
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while len(q) != 0:
        tmp_y, tmp_x = q.popleft()
        
        for i in range(4):
            next_y = tmp_y + y_diff[i]
            next_x = tmp_x + x_diff[i]
            if ( 0 <= next_x <= w-1 
                    and 0 <= next_y <= h-1 
                    and check[next_y][next_x] == 0 
                    and a[next_y][next_x] != '
                check[next_y][next_x] = 1 
                require[next_y][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])
                
    return require


h, w = MI()
a = [IS() for _ in range(h)]



out = 0
que = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '
            que.append([i,j])


ans = bfs(que)

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


print(out)

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

stack = deque([])
for h in range(H):
    for w in range(W):
        if maze[h][w]=="
            stack.append((h,w))
            dist[h][w] = 0

ans = 0
while stack:
    ch,cw = stack.popleft()
    ans = max(ans, dist[ch][cw])
    for y,x in zip([0,0,-1,1], [1,-1,0,0]):
        nh,nw = ch+y, cw+x
        if not(0 <= nh < H and 0 <= nw < W):
            continue
        if dist[nh][nw] == None:
            stack.append((nh,nw))
            dist[nh][nw] = dist[ch][cw] + 1
        else:
            dist[nh][nw] = min(dist[nh][nw], dist[ch][cw] + 1)

print(ans)

Solution (Python):
def main():
    from collections import deque
    H, W = map(int, input().split())
    grid = [["
                                for i in range(H)] + [["
    
    stack = deque()
    for h in range(1, H+1):
        for w in range(1, W+1):
            
            if grid[h][w] == "
                stack.append([h, w])

    for i in range(h + w + 3):
        tmp = deque()
        while stack:
            h, w = stack.pop()
            for dh, dw in ([0, 1], [0, -1], [1, 0], [-1, 0]):
                if grid[h + dh][w + dw] == ".":
                    grid[h + dh][w + dw] = "
                    tmp.append([h + dh, w + dw])
        stack = tmp
        if not stack:
            print(i)
            break


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "
A = np.array(A)

for i in range(H-1):
  A[i+1, :] = np.minimum(A[i, :] + 1, A[i+1, :])
for i in range(H-1,0,-1):
  A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
  A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
  A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))

Solution (Python):
from collections import deque

def solve():
    H, W = map(int, input().split())
    Ass = ['

    distss = [[-1]*(W) for _ in range(H)]
    Q = deque([])
    for i in range(1, H+1):
        for j in range(1, W+1):
            if Ass[i][j] == '
                Q.append((i, j))
                distss[i-1][j-1] = 0

    while Q:
        i, j = Q.popleft()
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            i2, j2 = i+di, j+dj
            if Ass[i2][j2] == '.' and distss[i2-1][j2-1] == -1:
                Q.append((i2, j2))
                distss[i2-1][j2-1] = distss[i-1][j-1] + 1

    return max(map(max, distss))

print(solve())

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    inf = h * w
    dp = [[inf for j in range(w)] for i in range(h)]

    q = deque()
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij == '
                q.append((i, j))
                dp[i][j] = 0

    dijs = list(zip([-1, 0, 1, 0], [0, -1, 0, 1]))
    while q:
        i, j = q.popleft()
        for di, dj in dijs:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if dp[ni][nj] <= dp[i][j] + 1: continue
            q.append((ni, nj))
            dp[ni][nj] = dp[i][j] + 1

    print(max(max(dpi) for dpi in dp))

main()

Solution (Python):
H, W = map(int, input().split())
func = (lambda x: 1 if x == "
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ

print(ans)

Solution (Python):
H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "
    ans += 1
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[[] for _ in range(h)]
for i in range(h):
    s=input()
    for j in s:
        if j=='.':
            a[i].append(-1)
        else:
            a[i].append(0)

def bfs():
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    q=deque()
    c=0
    for i in range(h):
        for j in range(w):
            if a[i][j]==0:
                q.append((i,j))
    while(len(q)>0):
        cur=q.popleft()
        i,j=cur
        for dd in d:
            di,dj=dd[0],dd[1]
            if (i+di)*(h-1-i-di)>=0 and (j+dj)*(w-1-j-dj)>=0 and a[i+di][j+dj]<0:
                c=a[i][j]+1
                a[i+di][j+dj]=c
                q.append((i+di,j+dj))
    return(c)

print(bfs())

Solution (Python):
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  f=[-1]*h*w
  q=deque()
  a,p=q.append,q.popleft
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='
      a(i)
      f[i]=0
  while q:
    i=p()
    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:
      a(j)
      f[j]=v
    if k>=0 and f[k]<0:
      a(k)
      f[k]=v
    if w>u+1and f[l]<0:
      a(l)
      f[l]=v
    if u and f[m]<0:
      a(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Solution (Python):
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  f=[-1]*h*w
  q=deque()
  a,p=q.append,q.popleft
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='
      a(i)
      f[i]=0
  while q:
    i=p()
    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:
      a(j)
      f[j]=v
    if k>=0 and f[k]<0:
      a(k)
      f[k]=v
    if w>u+1and f[l]<0:
      a(l)
      f[l]=v
    if u and f[m]<0:
      a(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Solution (Python):
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+1and f[l]<0:
      q.append(l)
      f[l]=v
    if u and f[m]<0:
      q.append(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Solution (Python):
from collections import*
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
grid=[["

stack=deque([])
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=deque([])
    while stack:
        my,mx=stack.pop()
        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):


import sys
import datetime
today = datetime.datetime.today

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [[True] * (W + 2)] + [[True] + [s == '
    q = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == True:
                q.append((i, j))
    rec = 0
    while len(q) > 0:
        q2 = []
        for i0, j0 in q:
            i, j = i0 - 1, j0
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0 + 1, j0
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0, j0 - 1
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
            i, j = i0, j0 + 1
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()

Solution (Python):
from collections import deque

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

m = [['X'] * (W+2)]
for i in range(H):
  row = [c for c in input()]
  row.insert(0, 'X')
  row.append('X')
  m.append(row)
m.append(['X'] * (W+2))

q = deque([deque([(i, j) for j in range(1, 1+W) for i in range(1, 1+H) if m[i][j] == '

cnt = 0
while(True):
  if not q:
    break
  tt = q.popleft()
  nn = deque([])
  for t in tt:
    
    for n in ((t[0]-1, t[1]), (t[0]+1, t[1]), (t[0], t[1]-1), (t[0], t[1]+1)):
      if m[n[0]][n[1]] == '.':
        nn.append(n)
        m[n[0]][n[1]] = '
  if nn:
    q.append(nn)
  cnt += 1

print(cnt-1)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        reached[i][j] = 0
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for y, x in zip(dy, dx):
        ny = py + y
        nx = px + x
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx] == -1:        
            que.append([ny, nx])
            reached[ny][nx] = reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
que = deque()

blck = [1] * (w + 2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [0] * (w+2)
    lineN[0] = 1
    lineN[-1] = 1
    for r, letter in zip(range(1, w+1), line):
        if letter == '
            lineN[r] = 1
            que.append((ln, r))
    data.append(lineN)
data.append(blck)


count = 0
next = deque()
while len(que) > 0:
    count += 1
    while len(que) > 0:
        r, c = que.popleft()

        r -= 1
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1

        r += 2
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1

        r-=1
        c-=1
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1

        c+=2
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1
    que, next = next, que

print(count - 1)

Solution (Python):
h,w=map(int,input().split())
l=[['
l[1:1]=[list('
p=[]
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='
      p.append([i,j])
d=[[-1,0],[1,0],[0,-1],[0,1]]
r=-1
while len(p)!=0:
  r+=1
  s=[]
  for i, j in p:
    for di, dj in d:
      di+=i
      dj+=j
      if l[di][dj]=='.':
        l[di][dj]='
        s.append([di,dj])
  p=s
print(r)

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

for h in range(1, H):
    counts[h, :] = np.minimum(counts[h, :], counts[h - 1, :] + 1)
    counts[-1 - h, :] = np.minimum(counts[-1 - h, :], counts[-h, :] + 1)
for w in range(1, W):
    counts[:, w] = np.minimum(counts[:, w], counts[:, w - 1] + 1)
    counts[:, -1 - w] = np.minimum(counts[:, -1 - w], counts[:, -w] + 1)

print(int(np.max(counts)))

Solution (Python):
h,w=map(int,input().split())
l=[['
l[1:1]=[list('
p=[]
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='
      p.append((i,j))
d=[(-1,0),(1,0),(0,-1),(0,1)]
r=-1
while len(p)!=0:
  r+=1
  s=[]
  for i, j in p:
    for di, dj in d:
      di+=i
      dj+=j
      if l[di][dj]=='.':
        l[di][dj]='
        s.append((di,dj))
  p=s
print(r)

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

L=[]
Q=deque()
for i in range(H):
    a=list(input())
    for j in range(W):
        if a[j]==".":
            a[j]=10000
        else:
            a[j]=0
            Q.append([i,j,0])
    L.append(a)
    



cnt=0
X=[1,-1,0,0]
Y=[0,0,1,-1]
for i in range(10**6+5):
    if len(Q)==0:
        break
    else:
        
        QZ=Q.popleft()
        for j in range(4):
            
            if (QZ[0]+1)<=(H-1) and j==0:
                
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<QZ[2]+1:
                        cnt=Q[0][2]+1
            if (QZ[0]-1)>=(0) and j==1:
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<QZ[2]+1:
                        cnt=QZ[2]+1
            if (QZ[1]+1)<=(W-1) and j==2:
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<Q[0][2]+1:
                        cnt=Q[0][2]+1
            if (QZ[1]-1)>=(0) and j==3:
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<QZ[2]+1:
                        cnt=QZ[2]+1
        
      

print(cnt)

Solution (Python):
import numpy as np
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([0 if i == "
A = np.array(A)
for i in range(H-1):
    A[i+1,:] = np.minimum(A[i,:]+1,A[i+1,:])
for i in range(H-1,0,-1):
    A[i-1,:] = np.minimum(A[i,:]+1,A[i-1,:])
for i in range(W-1):
    A[:,i+1] = np.minimum(A[:,i]+1,A[:,i+1])
for i in range(W-1,0,-1):
    A[:,i-1] = np.minimum(A[:,i]+1,A[:,i-1])
print(np.max(A))

Solution (Python):
import functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    
    
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)

Solution (Python):
import sys
import random
import itertools
sys.setrecursionlimit(20000000)

h, w = map(int,input().split())
a = [[j for j in input()] for i in range(h)]
def osen(x,y):
    global kuro2
    if x >0 and a[x-1][y] == ".":
        kuro2.append([x-1,y])
        a[x-1][y] = "
    if x < h-1 and a[x+1][y] == ".":
        kuro2.append([x+1,y])
        a[x+1][y] = "

    if y >0 and a[x][y-1] == ".":
        kuro2.append([x,y-1])
        a[x][y-1] = "
    if y < w-1 and a[x][y+1] == ".":
        kuro2.append([x,y+1])
        a[x][y+1] = "



kuro = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            kuro.append([i,j])
ans = 0
while kuro:
    kuro2 = []
    while kuro:
        x,y = kuro.pop()
        osen(x,y)
    kuro = kuro2
    ans += 1

print(ans-1)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
INF=10**9
check=[]
for i in range(h):
    sub_list=[]
    for j in range(w):
        sub_list.append(INF)
    check.append(sub_list)
black=deque([])
for i in range(h):
    sub_list=list(input())
    for j in range(w):
        if sub_list[j]=='
            black.append((i,j))
            check[i][j]=0
Max=0
while len(black)>0:
    now=black.popleft()
    U=(now[0]-1,now[1])
    D=(now[0]+1,now[1])
    L=(now[0],now[1]-1)
    R=(now[0],now[1]+1)
    for i in U,D,L,R:
        if 0<=i[0]<=h-1 and 0<=i[1]<=w-1 and check[i[0]][i[1]]==INF:
            check[i[0]][i[1]]=check[now[0]][now[1]]+1
            Max=max(Max,check[i[0]][i[1]])
            black.append(i)
print(Max)

Solution (Python):
from collections import deque
H, W = map(int ,input().split())
A = [input() for _ in range(H)]
dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
inf = float("inf")

dp = [[inf]*W for _ 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) or (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))

Solution (Python):
import numpy as np

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

max_value = H+W
values =[]


for i in range(H):
    values.append([0 if i == '

values = np.array(values)


for x in range(W-1):
    values[:,x+1] = np.minimum(values[:,x]+1,values[:,x+1])
for x in range(W-1,0,-1):
    values[:,x-1] = np.minimum(values[:,x-1],values[:,x]+1)
for x in range(H-1):
    values[x+1,:] = np.minimum(values[x,:]+1,values[x+1,:])
for x in range(H-1,0,-1):
    values[x-1,:] = np.minimum(values[x,:]+1,values[x-1,:])
print(np.max(values))

Solution (Python):
from collections import deque

H,W = map(int, input().split())
maze = [input() for _ in range(H)]
visited = [[False]*W for _ in range(H)]
q = deque([])


for h in range(H):
    for w in range(W):
        if maze[h][w] == "
            q.append((h,w,0))
            visited[h][w] = True

ans = 0
while q:
    h,w,d = q.popleft()
    for dy,dx in zip([0,0,-1,1], [-1,1,0,0]):
        nh, nw = h+dy, w+dx
        if not(0<=nh<H and 0<=nw<W):
            continue
        if not visited[nh][nw]:
            q.append((nh,nw,d+1))
            visited[nh][nw] = True
            ans = max(ans, d+1)

print(ans)

Solution (Python):

def a_darker_and_darker(H, W, Grid):
    from scipy.ndimage import distance_transform_cdt
    
    
    
    

    grid = [[1 if c == '.' else 0 for c in row] for row in Grid]
    return distance_transform_cdt(grid, metric='taxicab').max()

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(a_darker_and_darker(H, W, Grid))

Solution (Python):
h, w = map(int, input().split())
g = [[True]*(w+2)]
for i in range(h):
    g.append([True] + [a == '
g.append([True]*(w+2))

bp = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i][j]:
            bp.append((i, j))

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append((i+1, j))
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append((i-1, j))       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append((i, j+1))
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append((i, j-1))
    cnt += 1
    bp = p
print(cnt-1)