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())
al = [input() for _ in range(h)]

inf = 10**9
f = [[inf]*w for _ in range(h)]
q = deque()
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="
            f[hi][wi] = 0
            q.append((hi,wi))

while len(q)>0:
    hi,wi = q.popleft()
    c = f[hi][wi]

    for dh,dw in [[0,1],[1,0],[0,-1],[-1,0]]:
        nh = hi+dh
        nw = wi+dw
        if h>nh>=0 and w>nw>=0:
            if f[nh][nw]>c+1:
                f[nh][nw] = c+1
                q.append((nh,nw))

res = 0
for hi in range(h):
    for wi in range(w):
        res = max(res,f[hi][wi])
print(res)

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

h, w = map(int, input().split())
M = []
q = []
for i in range(h):
    line = input().strip()
    M.append(list(line))
    for j in range(w):
        if line[j] == "
            M[i][j] = 0
            q.append((j, i))

dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
cnt = 0
while q:
    next_q = []
    cnt += 1
    for x, y in q:
        for dx,dy in dir:
            next_x, next_y = x + dx, y + dy
            if 0 <= next_y <= h - 1 and 0 <= next_x <= w - 1:
                if M[next_y][next_x] == ".":
                    M[next_y][next_x] = M[y][x] + 1
                    q.append((next_x, next_y))
    q = next_q

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

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

while que:
    kuro=que.popleft()
    n=grid[kuro[0]][kuro[1]]
    for dx,dy in dirc:
        x=kuro[0]+dx
        y=kuro[1]+dy
        if 0<=x<h and 0<=y<w and grid[x][y]==-1:
            grid[x][y]=n+1
            que.append((x,y))

ans=0
for i in range(h):
    ans=max(ans,max(grid[i]))
print(ans)

Solution (Python):
from collections import deque

INF = float('inf')

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


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


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

while black_cells:
    y,x=black_cells.popleft()
    d=dist[y][x]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_x=x+dx
        new_y=y+dy
        if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
            continue
        if dist[new_y][new_x]==-1:
            dist[new_y][new_x]=d+1
            black_cells.append((new_y,new_x))
print(d)

Solution (Python):
from collections import deque

INF = float('inf')

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


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


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

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))
print(d)

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 i in range(H):
    for j in range(W):
        if grid[i][j]=="
            dist[i][j]=0
            black_cells.append((i,j))

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))
print(d)

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

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))
print(d)

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):
import sys
readline = sys.stdin.readline
from collections import deque
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = deque()
        for h, w in que:
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '
                    continue
                mat[h+dh][w+dw] = '
                next_que.append((h+dh, w+dw))

        res += 1
        que = next_que

    print(res - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = deque()
        for h, w in que:
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '
                    continue
                mat[h+dh][w+dw] = '
                next_que.append((h+dh, w+dw))

        res += 1
        que = next_que

    print(res - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = deque()
        for h, w in que:
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '
                    continue
                mat[h+dh][w+dw] = '
                next_que.append((h+dh, w+dw))

        res += 1
        que = next_que

    print(res - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = deque()
        for h, w in que:
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '
                    continue
                mat[h+dh][w+dw] = '
                next_que.append((h+dh, w+dw))

        res += 1
        que = next_que

    print(res - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        next_que = []
        while que:
            h, w = que.popleft()
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '
                    continue
                mat[h+dh][w+dw] = '
                next_que.append((h+dh, w+dw))

        res += 1
        que = deque(next_que)

    print(res - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))


def main():
    H, W = map(int, readline().rstrip().split())
    mat = [list(readline().rstrip()) for _ in range(H)]

    start = []
    for h in range(H):
        for w in range(W):
            if mat[h][w] == '
                start.append((h, w))
    
    res = 0
    que = deque(start)
    while que:
        flg = False
        next_que = deque()
        while que:
            h, w = que.popleft()
            for dh, dw in directions:
                if not (0 <= h+dh < H and 0 <= w+dw < W):
                    continue
                if mat[h+dh][w+dw] == '
                    continue
                flg = True
                mat[h+dh][w+dw] = '
                next_que.append((h+dh, w+dw))

        if flg:
            res += 1
        que = next_que

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)

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

area = [input() for _ in range(H)]

distance = [ [float('inf') for _ in range(W)] for _ in range(H)]
to_search = deque()
for i in range(H):
    for j in range(W):
        if area[i][j] == "
            to_search.appendleft((i, j, 0))
            distance[i][j] = 0
dist = [[1,0], [0,1], [-1,0], [0,-1]]
ans = 0
while len(to_search) > 0:
    nowi, nowj , nowd = to_search.pop()
    for di, dj in dist:
        nexti = nowi+di
        nextj = nowj+dj
        if 0<= nexti< H and 0<= nextj< W:
            if distance[nexti][nextj] > nowd+1:
                to_search.appendleft((nexti, nextj, nowd+1))
                distance[nexti][nextj] = nowd+1
                ans = max(ans, nowd+1)
print(ans)

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

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

print(bfs())

Solution (Python):
from collections import deque

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

infi = 10 ** 5
kouho = []
ans = [[infi] * (w) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if AA[i][j] == "
            kouho.append((i, j, 0))
            ans[i][j] = 0

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


que = deque(kouho)
while que:
    py, px, d = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if nx < 0 or nx >= w:
            continue
        if ny < 0 or ny >= h:
            continue
        if ans[ny][nx] == infi:
            ans[ny][nx] = d + 1
            que.append((ny, nx, d + 1))


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

print(cnt)

Solution (Python):
from collections import deque

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

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

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

ans = 0
while que:
    x, y = que.popleft()
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1:
            que.append((nx, ny))
            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())
A= [list(input()) for _ in range(H)]
d= [[2000 for _ in range(W)] for _ in range(H)]
move= [ (0,1),(0,-1),(1,0),(-1,0) ]
z= [[False for _ in range(W)] for _ in range(H)]
ans=0

v=deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            v.append( [i,j] )
            z[i][j]=True
            d[i][j]=0
while v:
    a=v.popleft()
    
    for mv in move:
        s=a[0]+mv[0]
        t=a[1]+mv[1]
        if 0<=s<H and 0<=t<W:
            if z[s][t]==False:
                z[s][t]=True
                d[s][t]=d[a[0]][a[1]]+1
                v.append([s,t])
                ans=max(ans,d[s][t])

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




H,W = IL()
S = SLs(H)

BL = []
for i in range(H):
  for j in range(W):
    if S[i][j] == "
      BL.append((i,j))
d = [[-1 for j in range(W)] for i in range(H)]
for i,j in BL:
  d[i][j] = 0
q = deque(BL)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while q:
  y,x = q.popleft()
  for i in range(4):
    nx,ny = x+dx[i], y+dy[i]
    if 0<=nx<W and 0<=ny<H:
      if d[ny][nx] == -1:
        d[ny][nx] = d[y][x] + 1
        q.append((ny,nx))
print(max(max(d[i][j] for j in range(W)) for i in range(H)))

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    A = [input().strip() for _ in range(H)]

    q = collections.deque()

    ans = [[0] * W for j in range(H)]

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

    while q:
        c = q.popleft()
        y, x, d = c[0], c[1], c[2]
        for ny, nx in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if 0 <= y + ny < H and 0 <= x + nx < W:
                if ans[y + ny][x + nx] == 0:
                    ans[y + ny][x + nx] = d + 1
                    q.append((y + ny, x + nx, d + 1))

    a = 0
    for aa in ans:
        a = max(a, max(aa))
    print(a)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
digtmp = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]

def main():
    H, W = map(int, input().split())
    grid = []; black = deque([])
    grid.append([0]*(W+2))
    for i in range(H):
        tmp = list(input()[:-1])
        for j in range(W):
            if tmp[j] == '
                black.append((i+1, j+1))
                tmp[j] = 0
        grid.append([0] + tmp + [0])
    grid.append([0]*(W+2))

    for _ in range(pow(10, 6)):
        fr = black.popleft()
        gfr = grid[fr[0]][fr[1]]
        for d in digtmp:
            to = (fr[0]+d[0], fr[1]+d[1])
            gto = grid[to[0]][to[1]]
            if gto == '.':
                grid[to[0]][to[1]] = gfr + 1
                black.append(to)
            elif gto != '
                if gfr + 1 < gto:
                    grid[to[0]][to[1]] = gfr + 1
                    black.append(to)
            else:
                pass
        if len(black) == 0:
            break
    
    ans = max(flatten_2dim(grid))
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

h,w = map(int,readline().split())
a = read().split()

color = [[0]*(w+2) for _ in range(h+2) ]
stack = []
for i in range(h):
    for j in range(w):
        if(a[i][j] == '
            color[i+1][j+1] = 1
            stack.append((i+1,j+1))

for i in range(h+2):
    color[i][0] = 1
    color[i][-1] = 1

for j in range(w+2):
    color[0][j] = 1
    color[-1][j] = 1

ans = -1
while(stack):
    ans += 1
    new_stack = []
    while(stack):
        i,j = stack.pop()
        for x,y in zip([0,0,-1,1],[-1,1,0,0]):
            x += i
            y += j
            if(color[x][y]==0):
                color[x][y] = 1
                new_stack.append((x,y))

    stack = new_stack[::]

print(ans)

Solution (Python):
from collections import deque


def bfs(que, maze, dis):
    max_x = len(maze[0])
    max_y = len(maze)

    while len(q) > 0:
        x, y, d = que.popleft()
        dxy = [[-1, 0], [1, 0], [0, 1], [0, -1]]

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

            if 0 > nx or max_x <= nx or 0 > ny or max_y <= ny:
                continue
            if maze[ny][nx] == "
                continue
            if dis[ny][nx] != -1:
                continue

            dis[ny][nx] = d + 1
            que.append([nx, ny, dis[ny][nx]])

    return


h, w = map(int, input().split())
maze = [[] for _ in range(h)]
distance = [[-1] * w for _ in range(h)]

for i in range(h):
    maze[i] = input()

q = deque()

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

bfs(q, maze, distance)

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

print(ans)

Solution (Python):
import sys

import math


from collections import deque


input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
p=((1,0),(-1,0),(0,1),(0,-1))
for x in range(h):
  for y in range(w):
    if a[x][y]=="
      b.append((x,y))
      n[x*w+y]=0
while b:
  x,y=b.popleft()
  for idx in p:
    s,t=idx
    if 0<=x+s<h and 0<=y+t<w:
      if n[(x+s)*w+(y+t)]==-1:
        n[(x+s)*w+(y+t)]=n[x*w+y]+1
        b.append((x+s,y+t))
print(max(n))

Solution (Python):
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    while que:
        p = que.popleft()
        y = p[0]
        x = p[1]

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    return dist



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


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


nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)

Solution (Python):
from collections import deque, Counter


def bfs():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 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 dist[ny][nx] == -1:
                dist[ny][nx] = dist[p[0]][p[1]] + 1
                que.append((ny, nx))

    return dist



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


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


nd = bfs()

ans = 0
for h in range(H):
    for w in range(W):
        if nd[h][w] > ans:
            ans = nd[h][w]

print(ans)

Solution (Python):
from collections import deque

import sys
input = sys.stdin.readline

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

H, W = map(int, input().split())
A = [input() for _ in range(H)]
dist = [-1 for _ in range(H * W)]

queue = deque()

for x in range(H):
    for y in range(W):
        if A[x][y] == '
            z = x * W + y
            queue.append(z)
            dist[z] = 0

while queue:
    z = queue.popleft()
    x, y = divmod(z, W)
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        nz = nx * W + ny
        if dist[nz] != -1:
            continue
        dist[nz] = dist[z] + 1
        queue.append(nz)

print(max(dist))

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

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "
                d[i][j] = 0
                q.append((i,j))
    a = 0

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
                a = max(a,d[nx][ny])
    return a

print(bfs())

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W = MI()
grid = [list(input()) for _ in range(H)]

seen = set()
q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '
            q.append((i, j, 0))
            seen.add(i * W + j)
while len(q) > 0:
    h, w, d = q.popleft()
    for dh, dw in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if 0 <= h + dh < H and 0 <= w + dw < W and (h + dh) * W + w + dw not in seen:
            q.append((h + dh, w + dw, d + 1))
            seen.add((h + dh) * W + w + dw)
print(d)

Solution (Python):
from collections import deque

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

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

Q = deque()
Q1 = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            D[i][j] = 1
            Q.append([i, j])

yudlr = [1, -1, 0, 0]
xudlr = [0, 0, -1, 1]

C = 0
while len(Q) > 0:
    C += 1
    while len(Q) > 0:
        Q1.append(Q.pop())
    while len(Q1) > 0:
        q = Q1.popleft()
        y = q[0]
        x = q[1]
        for i in range(4):
            y1 = y + yudlr[i]
            x1 = x + xudlr[i]
            if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                continue
            if D[y1][x1] == 1:
                continue
            D[y1][x1] = 1
            Q.append([y1, x1])

print(C - 1)

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

visited = [[False]*(W+2) for _ in range(H+2)]
dh = [0,1,0,-1]
dw = [1,0,-1,0]

from collections import deque
d = deque()

S = [0]*(H+2)
S[0] = '*'*(W+2)
S[H+1] = '*'*(W+2)
white = 0
for h in range(1,H+1):
    S[h] = '*' + input() + '*'
    for w in range(1,W+1):
        if S[h][w]=='
            visited[h][w]=True
            d.append((h,w,0))
    


while len(d)>0:
    h,w,cnt = d.popleft()
    for i in range(4):
        h0 = h+dh[i]
        w0 = w+dw[i]
        if S[h0][w0]=='.' and visited[h0][w0]==False:
            visited[h0][w0]=True
            d.append((h0,w0,cnt+1))
print(cnt)

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]
    grid = [[item for item in input()] for _ in range(H)]

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

    que = collections.deque()
    next_y_x = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    

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




    while que:
        temp = que.popleft()

        for dy, dx in next_y_x:
            ny = temp[0] + dy
            nx = temp[1] + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1:
                if fp[ny][nx] == -1:
                    que.append([ny, nx, temp[2]+1])
                    fp[ny][nx] = temp[2] + 1

    temp_max_list = []
    for line in fp:
        temp_max_list.append(max(line))

    print(max(temp_max_list))



if __name__ == "__main__":
    resolve()