Problem:
 Score : 300 points    Problem Statement You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is # if the square at the i -th row from the top and the j -th column from the left is black, and A_{ij} is . if that square is white.  We will repeatedly perform the following operation until all the squares are black:   Every white square that shares a side with a black square, becomes black.   Find the number of operations that will be performed.
The initial grid has at least one black square.      Constraints  1 \leq H,W \leq 1000  A_{ij} is # or . .  The given grid has at least one black square.         Input Input is given from Standard Input in the following format:  H  W  A_{11} A_{12} ... A_{1W}  :  A_{H1} A_{H2} ... A_{HW}       Output Print the number of operations that will be performed.        Sample Input 1 3 3
...
.#.
...      Sample Output 1 2  After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.       Sample Input 2 6 6
..#..#
......
#..#..
......
.#....
....#.      Sample Output 2 3

Solution (Python):
from collections import deque


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

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

checked = [[False for _ in range(W)] for _ in range(H)]

que = deque()
flag = False
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            que.append((i, j))
            checked[i][j] = True
        else:
            flag = True

if flag is False:
    print('0')
    exit()

n_que = deque()
step = 0
while len(que):

    h, w = que[0][0], que[0][1]
    que.popleft()
    for d in range(4):
        nh, nw = h + dy[d], w + dx[d]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if checked[nh][nw] is True:
            continue
        n_que.append((nh, nw))
        checked[nh][nw] = True

    if len(que) == 0:
        if len(n_que) == 0:
            print(step)
            exit()
        que = n_que
        n_que = deque()
        step += 1

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

Solution (Python):
from collections import deque
H, W = [int(x) for x in input().split()]
masu = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[-1] * W for i in range(H)]

def bfs():
    q = deque()
    for x in range(H):
        for y in range(W):
            if masu[x][y] == '
                q.append([x, y])
                d[x][y] = 0
    while q:
        x, y = q.popleft()
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == -1:
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    ans = -1
    for x in range(H):
        for y in range(W):
            ans = max(ans, d[x][y])
    return ans

print(bfs())

Solution (Python):
from collections import deque
import sys
from collections import defaultdict
import copy




H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1

        for temp in go:
            
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: 
                
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq
    nq = 0
    ans += 1
print(ans)

Solution (Python):
from collections import deque


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

maze = [list(input()) for i in range(H)]

black_cells = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j]=="
            black_cells.append((i,j))
            d[i][j] = 0

def bfs():
    
    
    

    
    s = 0
    while black_cells:
        p, q = black_cells.popleft()
        s = d[p][q]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = q + dx
            ny = p + dy
            
            if 0<=nx<W and 0<=ny<H and d[ny][nx]==-1:
                
                
                
                
                
                black_cells.append((ny, nx))
                d[ny][nx] = s + 1
                    
                        

    return s









print(bfs())

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 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):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(input()) 
def ifn(): return float(input()) 
def isn(): return input().split() 
def imn(): return map(int, input().split()) 
def fmn(): return map(float, input().split()) 
def iln(): return list(map(int, input().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, input().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD

H, W = imn()
count = [[-1 for _ in range(W)] for _ in range(H)]
queue = deque([])
A = []
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '
            queue.append((i,j))
            count[i][j] = 0
    A.append(list(s))

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
ans = 0
while len(queue) > 0:
    point = queue.popleft()
    for i in range(4):
        x = point[1] + dx[i]
        y = point[0] + dy[i]
        if x < 0 or x >= W or y < 0 or y >= H: continue
        if count[y][x] != -1: continue
        count[y][x] = count[point[0]][point[1]] + 1
        queue.append((y,x))
        ans = max(ans, count[y][x])
print(ans)

Solution (Python):
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque()

    cnt=h*w
    for x in range(w):
        for y in range(h):
            if l[y][x]=="
                cnt-=1
                Q.append([x,y])
    if cnt==0:
        return 0

    ans=0
    while True:
        nxtQ = deque()

        ans+=1
        while Q:
            p = Q.popleft()
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "
                        nxtQ.append([nx,ny])
                        cnt-=1
        Q=nxtQ
        if cnt<=0:
            return ans

print(solve())

Solution (Python):
import sys
from collections import deque

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

d = [[ sys.maxsize for b in range(W)] for a in range(H)]

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

q = deque()

for y in range(H):
  for x in range(W):
    if c[y][x] == '
      q.append([y, x])
      d[y][x] = 0
ans = 0
while len(q) > 0:
  y, x = q.popleft()
  for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and c[ny][nx] == '.' and d[ny][nx] == sys.maxsize:
      q.append([ny, nx])
      d[ny][nx] = d[y][x]+1
      ans = max(ans, d[ny][nx])

      
print(ans)

Solution (Python):
from collections import deque

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

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "
            black_cells.append((i, j))
            memo[i][j] = 0

count = 0
while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)

Solution (Python):

from collections import deque


def main():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    
    dist = [[-1] * W for _ in range(H)]

    ans = float('inf')
    que = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                que.append([h, w])
                dist[h][w] = 0

    
    while len(que) > 0:
        v = que.popleft()  
        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and dist[nx][ny] == -1):
                que.append([nx, ny])
                dist[nx][ny] = dist[v[0]][v[1]] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, dist[h][w])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    
    painted = [['
    painted += [['
    painted.append(['
    que = []

    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if painted[y][x] == '
                painted[y][x] = 0
                que.append((y, x))
    while que:
        qq = []
        for y, x in que:
            if painted[y - 1][x] == '.':
                painted[y - 1][x] = painted[y][x] + 1
                qq.append((y - 1, x))
            if painted[y + 1][x] == '.':
                painted[y + 1][x] = painted[y][x] + 1
                qq.append((y + 1, x))
            if painted[y][x + 1] == '.':
                painted[y][x + 1] = painted[y][x] + 1
                qq.append((y, x + 1))
            if painted[y][x - 1] == '.':
                painted[y][x - 1] = painted[y][x] + 1
                qq.append((y, x - 1))
        que = qq

    print(painted[y][x])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = list(map(int, input().split()))
    c = [input() for j in range(H)]
    from collections import deque
    que = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                que.append((h, w))
                dist[h][w] = 0
 
    def bfs():
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            
            
            cy, cx = que.popleft()
            for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ny, nx = cy+dy, cx+dx
                if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1 and c[ny][nx] == '.':
                    dist[ny][nx] = dist[cy][cx] + 1
                    que.append((ny, nx))
 
    bfs()
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, dist[h][w])
    print(ans)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    from collections import deque
    que = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                que.append((h, w))
                dist[h][w] = 0

    def bfs():
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    bfs()
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, dist[h][w])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    from collections import deque
    que = deque()
    dist = [[-1]*W for i in range(H)]
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                que.append((h, w))
                dist[h][w] = 0

    def bfs():
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    bfs()
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, dist[h][w])
    print(ans)


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
H, W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
seen = [[False]*W for _ in range(H)]
ans = 0
dq = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            dq.append((i, j, 0))
            seen[i][j] = True
while len(dq):
    x, y, d = dq.popleft()
    ans = max(ans, d)
    for nx, ny in [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]:
        if 0 <= nx < H and 0 <= ny < W:
            if not seen[nx][ny]:
                dq.append((nx, ny, d+1))
                seen[nx][ny] = True
print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    F = [[False for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if S[h][w] == "
                F[h][w] = True
    ans = 0
    q = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == "
                q.append((w, h))
    while q != []:
        r = []
        for n in q:
            DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
            for d in DIR:
                x, y = n[0] + d[0], n[1] + d[1]
                if 0 <= x < W and 0 <= y < H:
                    if F[y][x] == False:
                        F[y][x] = True
                        r.append((x, y))
        if r == []:
            break
        q = r
        ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(1000000)
h, w = map(int, input().split())
field = []
for _ in range(h):
    field.append(list(input()))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
distance = [[-1] * w for i in range(h)]

que = deque([])
for y in range(h):
    for x in range(w):
        if field[y][x] == '.':
            continue
        que.append([y, x])
        distance[y][x] = 0

while que:
    q = que.popleft()
    for i in range(4):
        now_y = q[0] + dy[i]
        now_x = q[1] + dx[i]
        if now_y < 0 or now_y >= h or now_x < 0 or now_x >= w or field[now_y][now_x] == '
            continue
        if distance[now_y][now_x] != -1:
            continue
        que.append([now_y, now_x])
        distance[now_y][now_x] = distance[q[0]][q[1]] + 1

draw_count = 0
for y in range(h):
    for x in range(w):
        draw_count = max(draw_count, distance[y][x])
print(draw_count)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = deque(q)
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '
                    q.append((ti, tj))
print(ans)

Solution (Python):
from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))

Solution (Python):
height, width = map(int, input().split(" "))
target = []
queue = []
WHITE = "."
BLACK = "
for h in range(height):
    temp = [n for n in input()]
    for w in range(width):
        if temp[w] == BLACK:
            queue.append([w, h])
    target.append(temp)
all_move = [[0, 1], [0, -1], [1, 0], [-1, 0]]

answer = 0
while queue:
    next_queue = []
    for q in queue:
        here_x, here_y = q
        for x, y in all_move:
            next_x, next_y = here_x + x, here_y + y
            if 0 <= next_x < width and 0 <= next_y < height:
                if target[next_y][next_x] == WHITE:
                    next_queue.append([next_x, next_y])
                    target[next_y][next_x] = BLACK
    if not next_queue:
        print(answer)
        break
    queue = next_queue
    answer += 1

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

def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()

"""))

Solution (Python):
from itertools import product
from collections import deque

H, W = [int(i) for i in input().split()]
grid = [list(input()) for _ in range(H)]
reached = [[0] * W for _ in range(H)]

queue = deque()
for y, x in product(range(H), range(W)):
    if grid[y][x] == "
        queue.append((y, x, 0))

if len(queue) == H * W:
    print(0)
    exit()

while queue:
    y, x, steps = queue.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        ny, nx = y + dy, x + dx
        if not (0 <= ny < H and 0 <= nx < W):
            continue
        if reached[ny][nx]:
            continue
        reached[ny][nx] = 1
        queue.append((ny, nx, steps+1))
print(steps)

Solution (Python):
from collections import deque


dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]


max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    
    s.append(list("


s = [list("
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

queue = deque()
for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '
            queue.append((i, j))

while queue:
    
    h, w = queue.popleft()

    
    for i in range(4):

        
        dx, dy = dis_x[i], dis_y[i]

        
        if s[h+dy][w+dx] == '.':
            s[h+dy][w+dx] = '
            dist[h+dy][w+dx] = dist[h][w] + 1

            queue.append((h+dy, w+dx))


print(max(max(l) for l in dist))

Solution (Python):
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    ans += 1
    qq = deque()
    while que:
      nh, nw = que.popleft()
      if nw < W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if nw > 0 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh < H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if nh > 0 and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    ans += 1
    qq = deque()
    while que:
      nh, nw = que.popleft()
      if nw < W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if nw > 0 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh < H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if nh > 0 and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Solution (Python):
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()

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

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

Solution (Python):
from collections import deque
def main():
  h,w=map(int,input().split())
  ans,q=0,deque()
  visited=[[0 if j=="
  q=deque([(i,j) for i in range(h) for j in range(w) if visited[i][j]==0])
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if visited[newx][newy]==-1:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()

Solution (Python):
from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()

Solution (Python):












from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        if (s[i][j] == "
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

print(ans)