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* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul
from bisect import* 
from heapq import* 
from math import factorial
from copy import deepcopy
import sys

sys.setrecursionlimit(10**6)



def main():
    h,w=map(int,input().split())
    stack=deque()
    grid=[["
    for i in range(h):
        tmp=[]
        for k,v in enumerate(input()):
            if v=="
                tmp.append("
                stack.appendleft((i+1,k+1))
            else:
                tmp.append(v)
        grid.append(["
    grid.append(["


    for i in range(h*w):
        tmp=deque()
        while stack:
            y,x=stack.pop()
            for my,mx in ((0,1),(1,0),(-1,0),(0,-1)):
                if grid[y+my][x+mx]==".":
                    grid[y+my][x+mx]="
                    tmp.appendleft((y+my,x+mx))
        stack=tmp
        if not len(stack):
            print(i)
            exit()
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):
import sys
import numpy as np



input = sys.stdin.readline

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

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    for j, c in enumerate(input()):
        if c == "
            status[i,j] = 0


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

print(np.max(status))

Solution (Python):

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

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

print(count)

Solution (Python):
H,W=map(int,input().split())
A=[[None]*(W+2)]
A.extend([[i=="." for i in "
A.append([None]*(W+2))


q=[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]

for k in range(2000):


    r=[]
    
    
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=None
            
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=None
            
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=None
            
            r.append((i,j+1))
    if not len(r):
        break
    q=r
print(k)

Solution (Python):
H,W=map(int,input().split())
A=[[None]*(W+2)]
A.extend([[i=="." for i in "
A.append([None]*(W+2))


q=[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]


k=0
while(q):
    r=[]
    
    
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=None
            
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=None
            
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=None
            
            r.append((i,j+1))
    if not len(r):
        break
    q=r
    k+=1
print(k)

Solution (Python):
H,W=map(int,input().split())
A=[[False]*(W+2)]+\
  [[i=="." for i in "
  [[False]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=False
            q[k+1].append((i-1,j))
            f=False
        if A[i+1][j]:
            A[i+1][j]=False
            q[k+1].append((i+1,j))
            f=False
        if A[i][j-1]:
            A[i][j-1]=False
            q[k+1].append((i,j-1))
            f=False
        if A[i][j+1]:
            A[i][j+1]=False
            q[k+1].append((i,j+1))
            f=False
    if f:
        break
print(k)

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

h, w = map(int, input().split())
map = [input() for _ in range(h)]
mapB = np.zeros((h, w))
for i, ii in enumerate(map):
  for j, jj in enumerate(ii):
    if jj == '.':
      mapB[i, j] = 1
dist = ndimage.distance_transform_cdt(mapB, metric="taxicab")
print(dist.max())

Solution (Python):
from collections import deque

h, w = map(int, input().split())
c = [list(input()) for _ in range(h)]

q = deque([])

for i in range(h):
    for j in range(w):
        if c[i][j] == '
            q.append([i, j])
            c[i][j] = 0

p = q.popleft()
max = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
while True:
    xx = p[0]
    yy = p[1]
    for i in range(4):
        x = xx + dx[i]
        y = yy + dy[i]
        if x < 0 or x > h - 1 or y < 0 or w - 1 < y:
            continue
        if c[x][y] == '.':
            q.append([x, y])
            count = c[xx][yy] + 1
            if max < count:
                max = count
            c[x][y] = count
    if len(q) == 0:
        break
    p = q.popleft()
print(max)

Solution (Python):

import sys
from scipy import ndimage
s = sys.stdin.readlines()
N, W = map(int, s[0].split())
W_matrix = [list(line.strip()) for line in s[1:N + 1]]
matrix_like_list = [[1 if x == "." else 0 for x in W_list] for W_list in W_matrix]
dist = ndimage.distance_transform_cdt(matrix_like_list, metric="taxicab")
print(dist.max())

Solution (Python):
from scipy.ndimage import*;print(morphology.distance_transform_cdt([[t>'

Solution (Python):

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

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if a[i][j]:
            q.append((i, j))

count = 0
while True:
    qq = []
    for i, j in q:
        if not a[i-1][j]:
            a[i-1][j] = True
            qq.append((i - 1, j))
        if not a[i+1][j]:
            a[i+1][j] = True
            qq.append((i + 1, j))
        if not a[i][j-1]:
            a[i][j-1] = True
            qq.append((i, j - 1))
        if not a[i][j+1]:
            a[i][j+1] = True
            qq.append((i, j + 1))
    q = qq
    if len(q) <= 0:
        break
    count += 1

print(count)

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
while cnt < H*W:
    d += 1
    tmp = []
    for sx, sy in Q:
        for x, y in zip(DX, DY):
            new_x = sx+x
            new_y = sy+y
            if 0 <= new_x < H and 0 <= new_y < W:
                if grid[new_x][new_y] == ".":
                    grid[new_x][new_y] = "
                    tmp.append([new_x, new_y])
                    cnt += 1
            else:
                continue
    Q = tmp

print(d)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0

while cnt < H*W:
    d += 1
    tmp = []
    
    
    
    
    
    for x, y in Q:
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = "
                    tmp.append([nx, ny])
                    cnt += 1
            else:
                continue
    Q = tmp

print(d)

Solution (Python):
from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)

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

grid = []
blacks = []
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == "
            blacks.append((i, idx))

c = 0
while len(blacks) > 0:
    c += 1

    new_blacks = []
    for b in blacks:
        top = b[0] - 1
        bottom = b[0] + 1
        left = b[1] - 1
        right = b[1] + 1

        if top >= 0:
            if grid[top][b[1]] == ".":
                grid[top][b[1]] = "
                new_blacks.append((top, b[1]))
        if bottom < H:
            if grid[bottom][b[1]] == ".":
                grid[bottom][b[1]] = "
                new_blacks.append((bottom, b[1]))
        if left >= 0:
            if grid[b[0]][left] == ".":
                grid[b[0]][left] = "
                new_blacks.append((b[0], left))
        if right < W:
            if grid[b[0]][right] == ".":
                grid[b[0]][right] = "
                new_blacks.append((b[0], right))

    blacks = new_blacks

print(c - 1)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
reached=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if c[i][j]=="
            stack.append((i,j))
            reached[i][j]=0
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="
            continue
        if reached[y][x]!=-1:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
        ans=max(ans,reached[y][x])
print(ans)

Solution (Python):



from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()

Solution (Python):






from collections import deque

h,w = map(int,input().split())
lis = [input() for x in range(h)]

vy = [0,0,1,-1]
vx = [1,-1,0,0]

reached = [[-1]*w for x in range(h)]
def bfs(bk_lis):
    q = deque()
    for i in bk_lis:
        q.append(i)
        reached[i[0]][i[1]]=0
    while q:
        y,x = q.popleft()
        for dy,dx in zip(vy,vx):
            ny,nx = y+dy,x+dx

            if not(0<=ny<h and 0<=nx<w):
                continue
            if  reached[ny][nx]==-1 or reached[ny][nx]>reached[y][x]+1:
                reached[ny][nx] = reached[y][x]+1
                q.append([ny,nx])

bk_lis = []
ans=0
for y in range(h):
    for x in range(w):
        if lis[y][x] == '
            bk_lis.append([y,x])

bfs(bk_lis)
for y in reached:
    ans = max(max(y),ans)


print(ans)

Solution (Python):

h,w=map(int,input().split())
s=[input() for _ in range(h)]

from collections import deque

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=deque()
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.popleft()
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)

Solution (Python):



def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

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

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

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

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[-1 for __ in range(w)] for _ in range(h)]
    blacks = deque()

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

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == -1:
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def sol():
    h,w=map(int,input().split())
    l=[]
    d=set()
    for i in range(h):
        s=list(input())
        for j in range(w):
            if s[j]=="
        l.append(s)
    ans=-1
    for i in range(2000):
        if len(d)==0: break
        ans+=1
        t=set()
        for j in d:
            if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
                l[j[0]+1][j[1]]="
                t.add((j[0]+1,j[1]))
            if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
                l[j[0]-1][j[1]]="
                t.add((j[0]-1,j[1]))
            if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
                l[j[0]][j[1]+1]="
                t.add((j[0],j[1]+1))
            if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
                l[j[0]][j[1]-1]="
                t.add((j[0],j[1]-1))
        d=t
    print(ans)

if __name__ == "__main__":
    sol()

Solution (Python):
H,W = [ int(it) for it in input().split() ]
li = [ [1 if it=="


po = []
for i in range(H):
  for j in range(W):
    if li[i][j]==1:
      po.append( (i,j) )
g = 0
for i in range(10000):
  po_ = []
  s = 0
  dw=[[0,1],[0,-1],[1,0],[-1,0]]
  for p,q in po:
    for dp,dq in dw:
      if ( 0<=p+dp and p+dp<H and 0<=q+dq and q+dq<W ):
        if (li[p+dp][q+dq]==0):
          s += 1
          li[p+dp][q+dq]=1
          po_.append( (p+dp,q+dq) )
  if (s==0):
    break
  else:
    g += 1
  po = po_
      

print (g)

Solution (Python):
import numpy as np

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

for i in range(1, H):
    a[i, :] = np.minimum(a[i, :], a[i-1, :] + 1)
for i in range(H - 2, -1, -1):
    a[i, :] = np.minimum(a[i, :], a[i+1, :] + 1)
for j in range(1, W):
    a[:, j] = np.minimum(a[:,j], a[:, j-1] + 1)
for j in range(W -2, -1, - 1):
    a[:, j] = np.minimum(a[:, j], a[:, j+1] + 1)

print(np.max(a))

Solution (Python):
from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break

Solution (Python):
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    q_list = []
    for i in range(h_len):
        tmp = [True]
        s_in = input()
        for j, s in enumerate(s_in):
            if s == '
                q_list.append((i+1, j+1))
                tmp.append(True)
            else:
                tmp.append(False)
        tmp.append(True)
        m_list.append(tmp)
    m_list.append([True for _ in range(w_len+2)])
    bfs(q_list)

Solution (Python):
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list):
        if 0 < h < h_len+1:
            for w, a in enumerate(w_list):
                if 0 < w < w_len + 1 and a:
                    q_list.append((h, w))
    bfs(q_list)

Solution (Python):
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)

Solution (Python):
from collections import deque
h,w=(int(i) for i in input().split())


a=[[i for i in input()] for j in range(h)]


cnt=0
ans=0
black=deque([])
for i in range(h):
    for j in range(w):
        if a[i][j]=='
            cnt+=1
            black.append((i,j))
dy=deque([1,0,-1,0])
dx=deque([0,1,0,-1])



while cnt<h*w:
    for i in range(len(black)):
        data=black.popleft()
        for j in range(4):
            if 0<=data[0]+dy[j]<h and 0<=data[1]+dx[j]<w:
                if a[data[0]+dy[j]][data[1]+dx[j]]=='.':
                    a[data[0]+dy[j]][data[1]+dx[j]]='
                    cnt+=1
                    black.append((data[0]+dy[j],data[1]+dx[j]))
    ans+=1
    
print(ans)

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):
def cnt(h,w):
  q=[]
  arr=[[True]*(w+2)]
  arr.extend([[True]+[s!='.' for s in input()]+[True] for _ in range(h)])
  arr.append([True]*(w+2))
  for i in range(1,h+1):
    for j in range(1,w+1):
      if arr[i][j]:
        q.append([i,j])
  ans=0
  while 1:
    nq=[]
    for y,x in q:
      if not arr[y-1][x]:
        nq.append((y-1,x))
        arr[y-1][x]=True
      if not arr[y][x-1]:
        nq.append((y,x-1))
        arr[y][x-1]=True
      if not arr[y+1][x]:
        nq.append((y+1,x))
        arr[y+1][x]=True
      if not arr[y][x+1]:
        nq.append((y,x+1))
        arr[y][x+1]=True
    if len(nq)==0:
      break
    else:
      q=nq
      ans+=1
  return ans
    
h,w=map(int,input().split())
print(cnt(h,w))

Solution (Python):
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('
for i in range(h):
  arr[i+1].append('
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('
for i in range(w+2):
  arr[h+1].append('
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='
  if len(q)==0:
    print(cnt)
    break

Solution (Python):


import sys

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() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def check(i, j, q, count, H, W, B, rec):
    if i < 0 or i >= H:
        return count
    if j < 0 or j >= W:
        return count
    if B[i][j] <= rec:
        return count
    B[i][j] = rec
    count += 1
    q.append((i, j))
    return count

def main():
    H, W = i2nn()
    A = ii2ss(H)
    HW = H * W
    B = [[3000] * W for _ in range(H)]
    q = []
    count = 0
    rec = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                B[i][j] = 0
                q.append((i, j))
                count += 1
    while True:
        if count >= HW:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, B, rec)
            count = check(i+1, j, q2, count, H, W, B, rec)
            count = check(i, j-1, q2, count, H, W, B, rec)
            count = check(i, j+1, q2, count, H, W, B, rec)
        q = q2

main()

Solution (Python):
def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            ti=t[i]
            if not ti[j+1]:
                ti[j + 1]=True
                nxt += [(i, j+1)]
            if not ti[j-1]:
                ti[j - 1]=True
                nxt += [(i, j-1)]
            if not t[i - 1][j]:
                t[i - 1][j]=True
                nxt += [(i - 1, j)]
            if not t[i + 1][j]:
                t[i + 1][j]=True
                nxt += [(i + 1, j)]
        kuro = nxt
    print(cnt)
 
 
h, w = map(int, input().split())
f(h, w)

Solution (Python):
import numpy as np

H, W = map(int, input().split())
val = []
INF = 10**9
for i in range(H):
    tmp = input()
    val.append([0 if tmp[j] == '
val = np.array(val)

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

print(val.max())

Solution (Python):
import numpy as np
from itertools import product
from collections import deque

H, W = map(int, input().split())
val = []
INF = 10**9
for i in range(H):
    tmp = input()
    val.append([0 if tmp[j] == '
val = np.array(val)

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

print(val.max())

Solution (Python):
import collections

h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]

INF = 10 ** 8
dist = [[INF] * w for _ in range(h)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def bfs():
    q = collections.deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '
                q.append((i, j))
                dist[i][j] = 0
                

    while len(q):
        py, px = q.popleft()
        for i in range(4):
            ny = py + dy[i]
            nx = px + dx[i]
            if -1 < ny < h and -1 < nx < w and grid[ny][nx] == '.' and dist[ny][nx] == INF:
                q.append((ny, nx))
                dist[ny][nx] = dist[py][px] + 1
                

    return max(max(dist, key=lambda x: max(x)))


if __name__ == '__main__':
    print(bfs())

Solution (Python):
from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)