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

Solution (Python):
from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
B = [[0 for _ in range(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,0))
            B[i][j] = 1
dmax = 0
while que:
    i,j,d = que.popleft()
    if j+1<W and B[i][j+1]==0:
        B[i][j+1]=d+1
        dmax = max(dmax,d+1)
        que.append((i,j+1,d+1))
    if i-1>=0 and B[i-1][j]==0:
        B[i-1][j]=d+1
        dmax = max(dmax,d+1)
        que.append((i-1,j,d+1))
    if j-1>=0 and B[i][j-1]==0:
        B[i][j-1]=d+1
        dmax = max(dmax,d+1)
        que.append((i,j-1,d+1))
    if i+1<H and B[i+1][j]==0:
        B[i+1][j]=d+1
        dmax = max(dmax,d+1)
        que.append((i+1,j,d+1))
print(dmax)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
As = [list(input()) for _ in range(H)]

from collections import deque
Q = deque()
dist = [[10**18]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if As[h][w]=='
            Q.append((h, w))
            dist[h][w] = 0

dirc = ((0, 1), (0, -1), (1, 0), (-1, 0))
while Q:
    y, x = Q.popleft()
    for dy, dx in dirc:
        ny, nx = y+dy, x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx]>dist[y][x]+1:
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny, nx))
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dist[h][w])
print(ans)

Solution (Python):
from collections import deque

tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

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

MAP = []

for _ in range(H):
    MAP.append(list(input()))

d = deque()

for i in range(H):
    for j in range(W):
        if MAP[i][j] == '
            d.append([i, j, 0])

ans = 0

while len(d) != 0:
    x, y, cnt = d.popleft()
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == '.':
            MAP[nx][ny] = '
            d.append([nx, ny, cnt + 1])
            ans = max(ans, cnt + 1)

print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
tizu = [list(input()) for _ in range(h)]
check = [[False for _ in range(w)] for _ in range(h)]
ans = 0

queue = deque()
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "
            queue.append([i, j])
            queue.append(0)
            check[i][j] = True

direct = [[1, 0], [-1, 0], [0, 1], [0, -1]]        
while queue:
    pos = queue.popleft()
    cnt = queue.popleft()
    for dy, dx in direct:
        n_y = pos[0] + dy
        n_x = pos[1] + dx
        if n_y == -1 or n_y == h or n_x == -1 or n_x == w:
            continue
        if check[n_y][n_x]:
            continue
        check[n_y][n_x] = True
        ans = max(ans, cnt + 1)
        queue.append([n_y, n_x])
        queue.append(cnt + 1)
print(ans)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy = [0, 1, 0, -1] 
    dx = [1, 0, -1, 0]
 
    que = deque([])
    for i in range(h):
        for j in range(w):
            if s[i][j] == '
                que.append((i, j))
                d[i][j] = 0

    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                ans = max(ans, d[ny][nx]) 
    return ans

h, w = MAP()
s = []
for i in range(h):
    s.append(input())
print(bfs())

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def solve(H, W, A):
    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)

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

    while queue:
        h, w = queue.popleft()
        d = dist[h][w]
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            y, x = h + i, w + j
            if dist[y][x] == -1:
                dist[y][x] = d + 1
                queue.append((y, x))

    res = max(map(max, dist))
    return res


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join((".", input().rstrip(), "."))

    ans = solve(H, W, A)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def solve(H, W, A):
    WALL = - 10 ** 7
    dist = [[WALL] + [-1] * W + [WALL] for _ in range(H + 2)]
    dist[0] = dist[-1] = [WALL] * (W + 2)

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

    while queue:
        h, w = queue.popleft()
        d = dist[h][w]
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            y, x = h + i, w + j
            if dist[y][x] == -1:
                dist[y][x] = d + 1
                queue.append((y, x))

    res = max(map(max, dist))
    return res


def main():
    H, W = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = list(input().rstrip())

    ans = solve(H, W, A)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys,math,collections,itertools,copy
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = []
dot_cnt = 0
for _ in range(H):
    a = input().rstrip()
    dot_cnt += a.count('.')
    s.append(list(a))

num_lis = [[float('inf')]*W for _ in range(H)]


for ih in range(H):
    for iw in range(W):
        if s[ih][iw]=='
            num_lis[ih][iw]=0
        else:
            if iw-1>=0:
                num_lis[ih][iw] = min(num_lis[ih][iw-1]+1,num_lis[ih][iw])
                
    for iw in range(W-1,-1,-1):
        
        if s[ih][iw]=='
            num_lis[ih][iw]=0
        else:
            if iw+1<=W-1:
                num_lis[ih][iw] = min(num_lis[ih][iw+1]+1,num_lis[ih][iw])


for iw in range(W):
    for ih in range(H):
        if s[ih][iw]=='
            num_lis[ih][iw]=0
        else:
            if ih-1>=0:
                num_lis[ih][iw] = min(num_lis[ih-1][iw]+1,num_lis[ih][iw])
                
    for ih in range(H-1,-1,-1):
        if s[ih][iw]=='
            num_lis[ih][iw]=0
        else:
            if ih+1<=H-1:
                num_lis[ih][iw] = min(num_lis[ih+1][iw]+1,num_lis[ih][iw])

maxOpe = 0
for iw in range(W):
    for ih in range(H):
        maxOpe = max(maxOpe,num_lis[ih][iw])
print(maxOpe)

Solution (Python):
from collections import deque
def bfs(al, h, w):
    q = deque([])
    visited = [ [-1]*w for _ in range(h) ]
    for i in range(h):
        for j in range(w):
            if al[i][j] == '
                q.append((i,j))
                visited[i][j] = 0

    while q:
        i, j = q.popleft()
        for ver, hor in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ni, nj = i+ver, j+hor
            if ni >= h or nj >= w or ni < 0 or nj < 0:
                continue
            if al[ni][nj] == '.' and visited[ni][nj] == -1:
                visited[ni][nj] = visited[i][j] + 1
                q.append((ni,nj))
    return visited


def main():
    h,w = map(int, input().split())
    al = []
    for _ in range(h):
        row = list(input())
        al.append(row)

    visited = bfs(al,h,w)
    ans = 0
    for v in visited:
        ans = max(max(v),ans)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
wall = '/'
grid = [[wall] * (w + 2)]
wn = 0

q = deque()
for y in range(1, h+1):
    grid.append([wall] + [c for c in input()] + [wall])
    for x in range(1, w+1):
        if grid[y][x] == '.':
            wn += 1
        if grid[y][x] == '
            q.append((y, x, 0))
grid.append([wall] * (w + 2))

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

while q:
    y, x, i = q.popleft()
    grid[y][x] = '
    for dy, dx in move:
        if grid[y + dy][x + dx] == '.':
            grid[y + dy][x + dx] = '
            q.append((y + dy, x + dx, i + 1))
    
print(i)

Solution (Python):
from collections import deque

h,w=list(map(int,input().split()))
a=[[c for c in input()] for _ in range(h)]
visit=[[0]*w for _ in range(h)]
q=deque()

for i in range(h):
    for j in range(w):
        if a[i][j]=='
            deque.appendleft(q,(i,j,0))
            visit[i][j]=1
ans=0
while len(q)>0:
    i,j,cnt=deque.pop(q)

    ans=max(ans,cnt)

    for di,dj in [(-1,0),(1,0),(0,-1),(0,1)]:
        ni=i+di
        nj=j+dj
        if 0<=ni<h and 0<=nj<w and visit[ni][nj]==0:
            visit[ni][nj]=1
            deque.appendleft(q,(ni,nj,cnt+1))

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
As = [list(input()) for _ in range(H)]
dist = [[10**18]*W for _ in range(H)]
dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))

from collections import deque
def bfs(start_lis):
    Q = deque()
    for sy, sx in start_lis:
        dist[sy][sx] = 0
        Q.append((sy, sx))
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny>=H or ny<0 or nx>=W or nx<0:
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.append((ny, nx))

start_lis = []
for h in range(H):
    for w in range(W):
        if As[h][w]=='
            start_lis.append((h, w))
bfs(start_lis)
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dist[h][w])
print(ans)

Solution (Python):


H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
black_list = []
for h in range(H):
    for w in range(W):
        if field[h][w] == "
            black_list.append((h, w))

count = 0
move = ((0, 1), (1, 0), (-1, 0), (0, -1))

while black_list:
    n_pl = []
    for b in black_list:
        for m in move:
            n_p = (b[0] + m[0], b[1] + m[1])
            if not(n_p[0] < 0 or n_p[1] < 0 or n_p[0] >= H or n_p[1] >= W) and field[n_p[0]][n_p[1]] == ".":
                field[n_p[0]][n_p[1]] = "
                n_pl.append(n_p)
    black_list = n_pl
    count += 1
print(count-1)

Solution (Python):
from collections import deque

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

dis = [[10000]*w for i in range(h)]
q = deque([])

for i in range(h):
    for j in range(w):
        if l[i][j] == "
            q.append([i,j,0])
            dis[i][j] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
while q:
    x,y,d = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and dis[nx][ny] > d+1:
            dis[nx][ny] = d + 1
            q.append([nx,ny,d+1])

ans = 0
for i in dis:
    ans = max(ans,max(i))
print(ans)

Solution (Python):
from collections import deque
INF=10**18
h,w=map(int,input().split())
e=[input() for _ in range(h)]
d=[[INF]*w for _ in range(h)]
q=deque([])
for i in range(h):
  for j in range(w):
    if e[i][j]=='
      q.append((i,j))
      d[i][j]=0
dx=[-1,0,1,0]
dy=[0,-1,0,1]
ans=0
while q:
  x,y=q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if 0<=nx<h and 0<=ny<w and e[nx][ny]=='.' and d[nx][ny]==INF:
      q.append((nx,ny))
      d[nx][ny]=d[x][y]+1
      ans=max(d[nx][ny],ans)
print(ans)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    table = []
    for _ in range(H):
        table.append(list(input()))
    frontier = []
    whites = H*W
    for i in range(H):
        for j in range(W):
            if table[i][j] == '
                frontier.append((i, j))
                whites -= 1
    count = 0
    while whites != 0:
        new_frontier = []
        for i, j in frontier:
            for i0, j0 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= i0 < H and 0 <= j0 < W and table[i0][j0] == '.':
                    table[i0][j0] = '
                    whites -= 1
                    new_frontier.append((i0, j0))
        frontier = new_frontier
        count += 1
    return count


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

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))




def main():
    h, w = ns()
    table = [list(input()) for _ in range(h)]
    not_visited = [[True for _ in range(w)] for __ in range(h)]
    dist = [[INF for _ in range(w)] for __ in range(h)]

    que = collections.deque()
    for hi in range(h):
        for wi in range(w):
            if table[hi][wi] == "
                not_visited[hi][wi] = False
                dist[hi][wi] = 0
                que.append([hi, wi])

    nxt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    cnt = -1
    ans = 0
    while len(que):
        cnt += 1
        for i in range(len(que)):
            hi, wi = que.popleft()
            for yi, xi in nxt:
                th = hi + yi
                tw = wi + xi
                if -1 < th < h and -1 < tw < w:
                    if not_visited[th][tw]:
                        not_visited[th][tw] = False
                        dist[th][tw] = min(dist[th][tw], dist[hi][wi] + 1)
                        que.append([th, tw])

    print(cnt)


if __name__ == '__main__':
    main()

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

matrix = []

visited = set()

for i in range(H):
    matrix.append(list(input()))

visited = set()

for i in range(H):
    for j in range(W):
        if matrix[i][j] == '
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '
                    continue
                visited.add((i+ud, j+lr))
                matrix[i+ud][j+lr] = '

res = 0

while visited:
    res += 1
    buf = set()
    for i, j in visited:
        if matrix[i][j] == '
            for ud, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                if not(0 <= i+ud < H and 0 <= j+lr < W)  or matrix[i+ud][j+lr] == '
                    continue
                buf.add((i+ud, j+lr))
                matrix[i+ud][j+lr] = '
    if not buf:
        break
    visited = buf

print(res)

Solution (Python):
from collections import deque

h,w=map(int, input().split())
a = [input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            black.append((i,j))
            visited[i][j] = 0

queue = deque(black)


while queue:
    y,x = queue.popleft()
    dydx = [[1,0],[-1,0],[0,1],[0,-1]]
    for j,k in dydx:
        newy,newx = y+j,x+k 
        if newy < 0 or newy >= h:continue 
        if newx < 0 or newx >= w:continue 
        if visited[newy][newx] == -1:
            visited[newy][newx] = visited[y][x] + 1
            queue.append((newy,newx))

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

print(ans)

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

A = [['

visited = [[True] * (W + 2) for _ in range(H + 2)]
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if A[h][w] == '.':
            visited[h][w] = False

que = []
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if visited[h][w]:
            que.append((h, w))

res = -1
while que:
    q = []
    res += 1
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        for x, y in que:
            nx, ny = x + dx, y + dy
            if not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
    que = q

print(res)

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

task = deque([])
visited = [[0 for _ in range(W)] for _ in range(H)]
cost = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
  for j in range(W):
    if A[i][j] == "
      task.append(((i,j),0))
      visited[i][j] = 1
      
black = 0
ans = 0
while task:
  p, c = task.popleft()
  cost[p[0]][p[1]] = c
  ans = max(ans,c)
  i = p[0]
  j = p[1]
  black += 1
  if i > 0 and visited[i-1][j] == 0 and A[i-1][j] == ".":
    task.append(((i-1,j),c+1))
    visited[i-1][j] = 1
  if j > 0 and visited[i][j-1] == 0 and A[i][j-1] == ".":
    task.append(((i,j-1),c+1))
    visited[i][j-1] = 1
  if i < H-1 and visited[i+1][j] == 0 and A[i+1][j] == ".":
    task.append(((i+1,j),c+1))
    visited[i+1][j] = 1
  if j < W-1 and visited[i][j+1] == 0 and A[i][j+1] == ".":
    task.append(((i,j+1),c+1))
    visited[i][j+1] = 1

print(ans if black == H*W else -1)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
V = [[-1]*w for _ in range(h)]
que = deque([])
for i,a in enumerate(A):
    for j,_a in enumerate(a):
        if _a == '
            que.append([i,j])
            V[i][j] = 0
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
while que:
    nwh,nww = que.popleft()
    for dh, dw in dhdw:
        if not (0<=nwh+dh<h and 0<=nww+dw<w): continue
        if V[nwh+dh][nww+dw] != -1: continue
        V[nwh+dh][nww+dw] = V[nwh][nww]+1
        que.append([nwh+dh, nww+dw])
print(max(map(max, V)))

Solution (Python):
from collections import deque

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

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

dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
while d:
    x1, y1 = d.popleft()

    for i in range(4):
        x2 = x1 + dx[i]
        y2 = y1 + dy[i]

        if 0 <= x2 < h and 0 <= y2 < w and dist[x2][y2] == -1:
            d.append([x2, y2])
            dist[x2][y2] = dist[x1][y1] + 1

print(max(list(map(lambda x: max(x), dist))))

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

g = []

for _ in range(H):
    g.append(list(input()))

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

for i in range(H):
    for j in range(W):
        if g[i][j] == "
            dist[i][j] = 0
            queue.append((j, i))

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

while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):
        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if g[adj_y][adj_x] == "
            continue

        if g[adj_y][adj_x] == ".":
            g[adj_y][adj_x] = "
            queue.append((adj_x, adj_y))
            dist[adj_y][adj_x] = dist[now_y][now_x] + 1

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

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                ans = max(ans,dist[nx][ny])
                d.append([nx,ny])

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)

Solution (Python):
from collections import deque

def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="
        for c in range(w):
            if a[r][c] == "
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

    h, w = map(int, readline().split())
    que = deque()
    grid = [[] for _ in range(h + 2)]
    grid[0] = ["
    grid[-1] = ["

    for row in range(1, h + 1):
        s = input()
        for col, c in enumerate(s, 1):
            if c == "
                que.append((row, col, 0))
        grid[row] = ["

    cnt = 0

    while que:
        cr, cc, cnt = que.popleft()
        if grid[cr + 1][cc] == ".":
            que.append((cr + 1, cc, cnt + 1))
            grid[cr + 1][cc] = "
        if grid[cr - 1][cc] == ".":
            que.append((cr - 1, cc, cnt + 1))
            grid[cr - 1][cc] = "
        if grid[cr][cc + 1] == ".":
            que.append((cr, cc + 1, cnt + 1))
            grid[cr][cc + 1] = "
        if grid[cr][cc - 1] == ".":
            que.append((cr, cc - 1, cnt + 1))
            grid[cr][cc - 1] = "
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict

    h, w = map(int, readline().split())
    que = deque()
    grid = [["

    for row in range(1, h + 1):
        s = input()
        for col, c in enumerate(s, 1):
            if c == "
                que.append((row, col, 0))
        grid.append(["

    grid.append(["
    direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    cnt = 0

    while que:
        cr, cc, cnt = que.popleft()
        for mr, mc in direction:
            nr, nc = cr + mr, cc + mc
            if grid[nr][nc] == ".":
                que.append((nr, nc, cnt + 1))
                grid[nr][nc] = "

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict

    h, w = map(int, readline().split())
    que = deque()
    grid = [["

    for row in range(1, h + 1):
        s = input()
        for col, c in enumerate(s, 1):
            if c == "
                que.append((row, col, 0))
        grid.append(["

    grid.append(["
    direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    cnt = 0

    while que:
        cr, cc, cnt = que.popleft()
        for mr, mc in direction:
            nr, nc = cr + mr, cc + mc
            if grid[nr][nc] == ".":
                que.append((nr, nc, cnt + 1))
                grid[nr][nc] = "

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
import copy


h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = [[False]*w for _ in range(h)]

c = []
d = [(-1,0), (1,0), (0,-1), (0,1)]
ans = 0

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


while True:
    tmp = []
    cnt = 0
    for i,j in c:
        for d1,d2 in d:
            if 0 <= i + d1 < h and 0 <= j + d2 < w:
                if not b[i+d1][j+d2]:
                    tmp.append((i+d1, j+d2))
                    b[i+d1][j+d2] = True
                    cnt += 1
    
    if cnt > 0:
        c = copy.copy(tmp)
        ans += 1
    else:
        break
    

print(ans)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        A_h = A[h]
        dist_h = dist[h]
        for w in range(W):
            if A_h[w] == "
                dist_h[w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def bfs(H, W, A, dist):
    queue = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                dist[h][w] = 0
                queue.append((h, w))
    while queue:
        h, w = queue.popleft()
        for y, x in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            next_h, next_w = h + y, w + x
            if dist[next_h][next_w] == -1:
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append((next_h, next_w))


def main():
    H, W = map(int, input().split())
    A = [None] * (H + 2)
    A[0] = A[-1] = "." * (W + 2)
    for i in range(1, H + 1):
        A[i] = "".join([".", input().rstrip(), "."])

    dist = [[0] + [-1] * W + [0] for _ in range(H + 2)]
    dist[0] = dist[-1] = [0] * (W + 2)
    bfs(H + 2, W + 2, A, dist)

    ans = max(map(max, dist))
    print(ans)


if __name__ == "__main__":
    main()