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):
def main():
  num_r,num_c = map(int,input().split())
  field = [input() for i in range(num_r)]
  q = []
  seen = [0]*(num_c*num_r)
  count = 0
 
  for i in range(num_r):
    for j in range(num_c):
      if field[i][j] == "
        seen[i*num_c+j] = 1
        q.append([i,j])
      
  while q:
    tank = []
    for i in q:
      r = i[0]
      c = i[1]
      if (0<=r-1) and (seen[(r-1)*num_c+c] == 0):
        tank.append([r-1,c])
        seen[(r-1)*num_c+c] = 1
      if (r+1<num_r) and (seen[(r+1)*num_c+c] == 0):
        tank.append([r+1,c])
        seen[(r+1)*num_c+c] = 1
      if (0<=c-1) and (seen[r*num_c+(c-1)] == 0):
        tank.append([r,c-1])
        seen[r*num_c+(c-1)] = 1
      if (c+1<num_c) and (seen[r*num_c+(c+1)] == 0):
        tank.append([r,c+1])
        seen[r*num_c+(c+1)] = 1
 
    count = count + 1
    q = tank
 
  print(count-1)
  
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())
 
    used = [True]*(h*w)
 
    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                p.append(i*w+j)
                used[i*w+j] = False
 
 
    
    res = 0
    while p:
        tank = []
        for e in p:
            if (e-w)>=0 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w-1 >= 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e+w<w*h and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w+1<w and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())
 
    used = [True]*(h*w)
 
    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                p.append(i*w+j)
                used[i*w+j] = False
 
 
    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)
 
if __name__ == '__main__':
    main()

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

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque()

for i in range(H):
    for j in range(W):
        if G[i][j] == '
            que.append([i, j])
cnt = -1
while que:
    cnt += 1
    next_que = deque()
    while que:
        h, w = que.popleft()  
        dh = [1, 0, -1, 0]
        dw = [0, 1, 0, -1]
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
                G[nh][nw] = '
                next_que.append([nh, nw])
    que = next_que
print(cnt)

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

q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            q.append((i, j))
ans = -1

while len(q) != 0:
    ans += 1
    qq = []
    while len(q) != 0:
        t = q.popleft()
        i,j = t[0],t[1]
        if i > 0 and A[i-1][j] == '.':
            qq.append((i-1,j))
            A[i-1][j] = '
        if j > 0 and A[i][j-1] == '.':
            qq.append((i,j-1))
            A[i][j-1] = '
        if i < H-1 and A[i+1][j] == '.':
            qq.append((i+1,j))
            A[i+1][j] = '
        if j < W-1 and A[i][j+1] == '.':
            qq.append((i,j+1))
            A[i][j+1] = '
    q = deque(qq)

print(ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
mz = []
q = deque()
for i in range(h):
    mz.append(list(input()))
    ls = [[i,j,0] for j, a in enumerate(mz[-1]) if a == '
    q.extend(ls)


delta = [[-1,0],[0,-1],[1,0],[0,1]]
while q:
    y,x,c = q.popleft()
    for dy,dx in delta:
        if (0<= y+dy <h) and (0<=x+dx <w):
            if mz[y+dy][x+dx] == ".":
                mz[y+dy][x+dx]="
                q.append([y+dy,x+dx,c+1])

            else: 
                pass

print(c)

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

has_visited = [[True]*(W+2)]
has_visited += [[True] + [m == "
has_visited += [[True]*(W+2)]

search_que = []
for y in range(1, H+1):
    for x in range(1, W+1):
        if has_visited[y][x]:
            search_que.append((y, x))

count = -1
while search_que:
    count += 1
    next_que = []
    for y, x in search_que:
        if not has_visited[y+1][x]:
            has_visited[y+1][x] = True
            next_que.append((y+1, x))
        if not has_visited[y-1][x]:
            has_visited[y-1][x] = True
            next_que.append((y-1, x))
        if not has_visited[y][x+1]:
            has_visited[y][x+1] = True
            next_que.append((y, x+1))
        if not has_visited[y][x-1]:
            has_visited[y][x-1] = True
            next_que.append((y, x-1))
    search_que = next_que

print(count)

Solution (Python):
import copy
from collections import deque


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


grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])



dist = [[0 for i in range(W)] for j in range(H)]


l_black = deque([])
for i in range(H):
  for j in range(W):
    if grid[i][j] == "
      l_black.append( [i,j] ) 


max_d = 0

while len(l_black) > 0:
  
  while len(l_black) > 0:
    v = l_black.popleft()
    
    for i in [ [v[0]+1,v[1]] , [v[0],v[1]+1] , [v[0]-1,v[1]] ,[v[0],v[1]-1] ]:
      
      if (i[1]<0 or i[0] <0 or i[0]>=H or i[1] >= W ):
        continue
      
      if grid[i[0]][i[1]] == "
        continue
      
      if grid[i[0]][i[1]] == ".":
        
        grid[i[0]][i[1]] = "
        
        l_black.append(i)
        
        dist[i[0]][i[1]] = dist[v[0]][v[1]] + 1
        max_d = max(max_d,dist[i[0]][i[1]])
print(max_d)

Solution (Python):
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

q = deque()
d = [[-1]*w for x in range(h)]

for i in range(h):
    for j in range(w):
        if m[i][j] == "
            q.append([i,j])
            d[i][j] = 0

aa = 0
while q:
    v = q.popleft()
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny = v[0] + i[0]
        nx = v[1] + i[1]
        if (0<=ny<h and 0<=nx<w and m[ny][nx] == "."):
            m[ny][nx] = "
            q.append([ny,nx])
            d[ny][nx] = d[v[0]][v[1]] + 1
            aa = max(aa,d[ny][nx])


print(aa)

Solution (Python):
from collections import deque

def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '
                and s[nextX][nextY] == '.':
                s[nextX][nextY] = s[p[0]][p[1]] + 1
                que.append([nextX, nextY])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

que = deque()
for i in range(H):
    for j in range(W):
        if s[i][j] == '
            que.append([i, j])
            s[i][j] = 0
bfs()
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])
print(ans)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '

bfs(q)
max_ans = 0
for i in range(H+2):
    
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)

Solution (Python):
from subprocess import call
call (('pypy3', '-c', """
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '

bfs(q)
max_ans = 0
for i in range(H+2):
    
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)
"""))

Solution (Python):
from sys import stdin
inf = 10**10
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
visited = [[0 for i in range(w)]for j in range(h)]
q = []
for i in range(h):
    for j in range(w):
        if li[i][j] == ".":
            continue
        q.append((i,j))
        visited[i][j] = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
while q:
    qq = []
    ans += 1
    for y,x in q:
        for i,j in zip(dy,dx):
            ny,nx = i+y,j+x
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            elif li[ny][nx] == "
                continue
            elif visited[ny][nx] == 0:
                visited[ny][nx] = 1
                qq.append((ny,nx))
    q = qq
print(ans)

Solution (Python):
from scipy.ndimage import distance_transform_cdt
H,W = map(int,input().split())
S = list(list(input()) for h in range(H))
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            S[h][w] = 0
        else:
            S[h][w] = 1
print(distance_transform_cdt(S, metric='taxicab').max())

Solution (Python):
def main():
    from collections import deque
    import sys
    

    

    H, W = map(int, sys.stdin.readline().split())
    field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

    

    queue = deque([])

    for h in range(H):
        for w in range(W):
            if field[h][w] == "
                queue.append([h, w])

    dist_from_nearest_black = [[0] * W for i in range(H)]
    direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

    def bfs():
        while len(queue) != 0:

            h, w = queue.popleft()

            for dh, dw in direction:
                next_h = h + dh
                next_w = w + dw

                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                elif field[next_h][next_w] == "
                    continue
                else:
                    dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                    field[next_h][next_w] = "
                    queue.append([next_h, next_w])

    bfs()

    ans = 0

    for d in dist_from_nearest_black:
        ans = max(ans, max(d))

    print(ans)
    


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys




H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]



queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)

Solution (Python):
from collections import deque
def bfs(A,H,W,D):
    que = deque(D)
    cnt = 0
    d = [-1,1]
    tmp = set()
    flag = 0
    while que:
        u = que.popleft()
        
        y,x = u
        for k in range(2):
            s = y + d[k]
            t = x + d[k]
            if 0 <= s < H:
                if A[s][x] == '.':
                    A[s][x] = '
                    tmp.add((s,x))
                    flag = 1
              
            if 0 <= t < W:
                if A[y][t] == '.':
                    A[y][t] = '
                    tmp.add((y,t))
                    flag = 1

            
        if not que:
            que = deque(tmp) 
            tmp = set()
            if flag:
                cnt += 1
            flag = 0
    return cnt

def main():
    H,W = map(int,input().split(" "))
    A = []
    D = []
    D_append = D.append
    for i in range(H):
        tmp = []
        for j,s in enumerate(input()):
            tmp.append(s)
            if s == '
                D_append((i,j))
        A.append(tmp)

    ans = bfs(A,H,W,D)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "
            visited[row][col] = 0
            queue.append((row, col, 0))
dist = 0
while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if row+drow>=0 and row+drow<h and col+dcol>=0 and col+dcol<w and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(dist)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "
            visited[row][col] = 0
            queue.append((row, col, 0))
dist = 0
while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(dist)

Solution (Python):
from collections import deque

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


dist = [[-1]*W for _ in range(H)]


black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Solution (Python):
from scipy.ndimage import distance_transform_cdt
H,W=map(int, input().split())
S=list(list(input()) for h in range(H))
for h in range(H):
    for w in range(W):
        if S[h][w]=="
            S[h][w]=0
        else:
            S[h][w]=1

print(distance_transform_cdt(S, metric='taxicab').max())

Solution (Python):
from subprocess import call
call(('pypy3','-c',"""
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans)     
"""))

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



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

while que:
    
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)

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

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



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

while que:
    
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)

Solution (Python):
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

from collections import deque
def bfs(maze):
    ans = 0
    d = [[-1] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if maze[i][j] == '
                que.append([i, j])
                d[i][j] = 0
    
    
    while que:
        y, x = que.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w  and 0 <= ny < h  and d[ny][nx] == -1 and maze[ny][nx] != "
                d[ny][nx] = d[y][x] + 1
                ans = max(ans, d[ny][nx])
                que.append([ny, nx])
                
    return ans

print(bfs(maze))

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


log=[[-1]*W for i in range(H)]
def bfs():
    task=deque([])
    
    for i in range(H):
        for j in range(W):
            if a[i][j]=='
                task.append((i,j))
                log[i][j]=0

    dh=[0,1,0,-1]
    dw=[1,0,-1,0]

    while task:
        h,w=task.popleft()
        
        for i in range(4):
            nh=h+dh[i]
            nw=w+dw[i]
            if not(0<=nh<H and 0<=nw<W):continue
            if a[nh][nw]=='
            a[nh][nw]='
            log[nh][nw]=log[h][w]+1
            task.append((nh,nw))

def ans_check():
    ans=0
    for i in range(H):
        for j in range(W):
            if ans<log[i][j]:ans=log[i][j]

    print(ans)

bfs()
ans_check()

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




log=[[-1]*W for i in range(H)]
def bfs():
    task=deque([])
    
    for i in range(H):
        for j in range(W):
            if a[i][j]=='
                task.append((i,j))
                log[i][j]=0

    dh=[0,1,0,-1]
    dw=[1,0,-1,0]

    while task:
        h,w=task.popleft()
        
        for i in range(4):
            nh=h+dh[i]
            nw=w+dw[i]
            if not(0<=nh<H and 0<=nw<W):continue
            if a[nh][nw]=='
            a[nh][nw]='
            log[nh][nw]=log[h][w]+1
            task.append((nh,nw))

def ans_check():
    ans=0
    for i in range(H):
        for j in range(W):
            if ans<log[i][j]:ans=log[i][j]

    print(ans)

bfs()
ans_check()

Solution (Python):
from collections import deque

h,w=map(int,input().split())
a = [input() for _ in range(h)]
move=((1,0),(0,1),(-1,0),(0,-1))

que=deque([])
visited=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            que.append((i,j,0))
            visited[i][j]=1


while len(que)>0:       
    ci,cj,d=que.popleft()
    for mi,mj in move:
        ni,nj=mi+ci,mj+cj
        if 0<=ni<h and 0<=nj<w and visited[ni][nj]==0:
            if a[ni][nj]==".":
                visited[ni][nj]=1
                que.append((ni,nj,d+1))

print(d)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
S=[input() for _ in range(H)]

paint=((1,0),(-1,0),(0,1),(0,-1))
que=deque([])

dark=[[0]*W for _ in range(H)] 

for i in range(H): 
    for j in range(W):
        if S[i][j]=='
            que.append((i,j,0))
            dark[i][j]=1
ans=0
while len(que)>0:
    di,dj,c=que.popleft()
    
    for pi,pj in paint:
        ni,nj=pi+di,pj+dj 
        if 0<=ni<H and 0<=nj<W and dark[ni][nj]==0:
            dark[ni][nj]=1
            que.append((ni,nj,c+1))
            ans=c+1
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, D[i][j])
print(ans)

Solution (Python):



'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)

Solution (Python):

"""
メモ型再起？
ダイクストラじゃあきつそう
1sec!?

各点高々1回しか選ばれない工夫が必要
qにいれて少しづつ進めてく？
→各点高々4回しか選択されない
"""


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

A = []
q = []

for i in range(H):

    a = list(input())
    A.append(a)

    for j in range(W):
        if a[j] == "
            q.append([i,j])

ans = 0
while len(q) > 0:

    
    
    nq = []
    flag = False

    for i,j in q:
        if i > 0 and A[i-1][j] == ".":
            A[i-1][j] = "
            nq.append([i-1,j])
            flag = True
        if i < H-1 and A[i+1][j] == ".":
            A[i+1][j] = "
            nq.append([i+1,j])
            flag = True
        if j > 0 and A[i][j-1] == ".":
            A[i][j-1] = "
            nq.append([i,j-1])
            flag = True
        if j < W-1 and A[i][j+1] == ".":
            A[i][j+1] = "
            nq.append([i,j+1])
            flag = True
    q = nq
    if flag:
        ans += 1


print (ans)

Solution (Python):
from collections import deque

def main():
    H,W = list(map(int,input().split()))
    A = [["
    for i in range(H):
        A.append(list("
    A.append(["

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

    ans = 0
    while queue:
        point = queue.popleft()
        ans = max(ans,point[2])
        for y,x in ((1,0),(0,1),(-1,0),(0,-1)):
            if A[point[0]+y][point[1]+x] == ".":
                A[point[0]+y][point[1]+x] = "
                queue.append((point[0]+y,point[1]+x,point[2]+1))
    print(ans)

if __name__ == "__main__":
    main()

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

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

if __name__ == "__main__":
    main()

Solution (Python):

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

import collections
from collections import deque

INF = -10 ** 9
distance = [[INF for i in range(w)] for j in range(h)]
d = deque()
def bfs():
    cnt=0
    while len(d):
        x, y = d.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if (0 <= nx <=h-1) and (0 <= ny<=w-1) and (distance[nx][ny] == INF):
                d.appendleft((nx, ny))
                distance[nx][ny] = distance[x][y] + 1
                if cnt<distance[nx][ny]:
                    cnt=distance[nx][ny]

    return cnt


for i in range(h):
    for j in range(w):
        if maze[i][j]=='
            d.append((i,j))
            distance[i][j]=0
print(bfs())

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[list(S()) for _ in range(h)]
  d=0

  q=collections.deque()
  nokori=h*w
  dist=[[-1]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if field[i][j]=='
        q.append((i,j))
        dist[i][j]=0
        nokori-=1

  while q:
    if nokori==0:
      return d

    y,x=q.popleft()

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and ny<h and 0<=nx and nx<w:
        if field[ny][nx]=='.':
          field[ny][nx]='
          d=dist[y][x]+1
          dist[ny][nx]=d
          q.append((ny,nx))
          nokori-=1

  return d


print(main())

Solution (Python):
from collections import deque

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

A = []
for i in range(H):
  A.append(input())
  
Q = deque()
visited = [[False for i in range(W)] for j in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == '
      Q.append([i,j,0])
      visited[i][j] = True

ans = 0
while len(Q) > 0:
  i,j,dist = Q.popleft()
  for dy, dx in [[1,0], [-1,0], [0,-1], [0,1]]:
    y = i + dy
    x = j + dx
    if y < 0 or H <= y or x < 0 or W <= x:
      continue
    if visited[y][x]:
      continue
    visited[y][x] = True
    Q.append([y,x,dist+1])
    ans = max(ans, dist+1)
    
print(ans)