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):
h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
c = 0
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "
            job.append((i, j))
            c += 1
ans = 0
while True:
    if c == h*w:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "
                    job2.append((yy,xx))
                    c += 1
    job = job2

Solution (Python):
def bfs():
   while len(que)>0:
      now=que.popleft()
      now_step=steps[now[0]][now[1]]
      for dy,dx in (-1,0),(1,0),(0,-1),(0,1):
         ny=now[0]+dy
         nx=now[1]+dx
         if 0<=ny<=H-1 and 0<=nx<=W-1:
            if maze[ny][nx]==".":
               maze[ny][nx]="
               que.append([ny,nx])
               steps[ny][nx]=now_step+1

from collections import deque

H,W=map(int,input().split())
maze=[]
for i in range(H):
   A=input()
   A=[c for c in A]
   maze.append(A)

steps=[[-1]*W for i in range(H)]
que=deque([])
for i in range(H):
   for j in range(W):
      if maze[i][j]=="
         que.append([i,j])
         steps[i][j]=0

bfs()

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

print(max_step)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]


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

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                
                que.append((ny, nx))
 
                ans = max(ans, d[ny][nx])     

    return ans


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

Solution (Python):
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "
      q.append((h+dh, w+dw, c+1))

print(ans)

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())
A = [list(input()) for _ in range(H)]
sharps = []
for h, line in enumerate(A):
    sharps += [[h, w, 0] for w, p in enumerate(line) if p == '

q = deque(sharps)
while q:
    i, j, score = q.popleft()
    for mi, mj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        ni = i + mi
        nj = j + mj
        if ni < 0 or H <= ni or nj < 0 or W <= nj or A[ni][nj] == '
            continue
        A[ni][nj] = '
        q.append([ni, nj, score+1])
print(score)

Solution (Python):

from collections import deque
h,w = map(int, input().split())
al = [input() for _ in range(h)]

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

while len(q)>0:
    ch,cw = q.popleft()
    c = m[ch][cw]
    for hi,wi in [[ch+1,cw],[ch,cw+1],[ch-1,cw],[ch,cw-1]]:
        if h>hi>=0 and w>wi>=0 and m[hi][wi]>c+1:
            m[hi][wi] = c+1
            q.append((hi,wi))

res = max([max(m[i]) for i in range(h)])
print(res)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
stack=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="
            stack.append([h,w,0])

stack=deque(stack)
value=0
while stack:
    h,w,m=stack.popleft()
    lst=[]
    if h>0:lst.append([-1,0])
    if h<H-1:lst.append([1,0])
    if w>0:lst.append([0,-1])
    if w<W-1:lst.append([0,1])
    n=m+1
    for y1,x1 in lst:
        Y=h+y1
        X=w+x1
        if A[Y][X]==".":
            A[Y][X]="
            stack.append([Y,X,n])
            if value<n:
                value=n
print(value)

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

dist = [[-1] * W for iii in range(H)]  
check_que = deque()

d = 0

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



def bfs(initial_d):  
    dis = 0
    
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)

print(dis)

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

H, W = map(int, input().split())
table = []
dist = [[-1]*W for i in range(H)]
Q = deque()
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0

for y in range(H):
    A = list(input())
    for x in range(W):
        if A[x] == "
            Q.append((y,x))
            dist[y][x] = 0
    table.append(A)

while Q:
    y,x = Q.popleft()
    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 and table[ny][nx] == ".":
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny,nx))
for i in range(H):
    ans = max(ans,max(dist[i]))
print(ans)

Solution (Python):
import copy
from collections import deque
H,W=map(int, input().split())
A=[[-1]*W for _ in range(H)]
d=deque()
for h in range(H):
  s=input()
  for w in range(W):
    if s[w]=='.':
      pass
    else:
      A[h][w]=0
      d.append((h,w))

DIF=[(1,0),(0,1),(-1,0),(0,-1)]
while d:
  point=d.popleft()
  for dif in DIF:
    x=point[0]+dif[0]
    y=point[1]+dif[1]
    if 0<=x<H and 0<=y<W and A[x][y]==-1:
      d.append((x,y))
      A[x][y]=A[point[0]][point[1]]+1
ans=0    
for h in range(H):
  Amax=max(A[h])
  ans=max(ans,Amax)

print(ans)

Solution (Python):
h, w = map(int, input().split())
lis = []
num = [[0] * w for i in range(h)]
s = [str(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            lis.append([i,j])
            num[i][j] = 1
cnt = -1
while lis != []:
    cnt += 1
    tmp = []
    for x,y in lis:
        if x > 0:
            if num[x-1][y] == 0:
                num[x-1][y] = 1
                tmp.append([x-1,y])
        if x < h-1:
            if num[x+1][y] == 0:
                num[x+1][y] = 1
                tmp.append([x+1,y])
        if y > 0:
            if num[x][y-1] == 0:
                num[x][y-1] = 1
                tmp.append([x,y-1])
        if y < w-1:
            if num[x][y+1] == 0:
                num[x][y+1] = 1
                tmp.append([x,y+1])
    lis = tmp
print(cnt)

Solution (Python):
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  M = [['

  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not M[bi - 1][bj]:
        M[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not M[bi][bj - 1]:
        M[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not M[bi + 1][bj]:
        M[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not M[bi][bj + 1]:
        M[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


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    A = [[c == '.' for c in s] for s in args[1:]]

    Q = deque()
    for y in range(h):
        for x in range(w):
            if not A[y][x]:
                Q.append((x, y, 0))

    ret = 0
    while Q:
        x, y, n = Q.popleft()

        ret = max(ret, n)
        if 0 < x and A[y][x-1]:
            Q.append((x-1, y, n+1))
            A[y][x-1] = False

        if x+1 < w and A[y][x+1]:
            Q.append((x+1, y, n+1))
            A[y][x+1] = False

        if 0 < y and A[y-1][x]:
            Q.append((x, y-1, n+1))
            A[y-1][x] = False

        if y+1 < h and A[y+1][x]:
            Q.append((x, y+1, n+1))
            A[y+1][x] = False

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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

q=deque()


for w in range(W):
    for h in range(H):
        if A[h][w]=='
            q.append((h,w,0))


ans=0
while q:
    h,w,d = q.popleft()
    ans=max(ans,d)
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        nh,nw = h+dh, w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if A[nh][nw]=='
            continue
        A[nh][nw]='
        q.append((nh,nw,d+1))

print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
A = [list(input().strip()) 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))
tot = 0
while que:
    i,j,cnt = que.popleft()
    if j+1<W and A[i][j+1]==".":
        A[i][j+1]="
        que.append((i,j+1,cnt+1))
        tot = cnt+1
    if j-1>-1 and A[i][j-1]==".":
        A[i][j-1]="
        que.append((i,j-1,cnt+1))
        tot = cnt+1
    if i+1<H and A[i+1][j]==".":
        A[i+1][j]="
        que.append((i+1,j,cnt+1))
        tot = cnt+1
    if i-1>-1 and A[i-1][j]==".":
        A[i-1][j]="
        que.append((i-1,j,cnt+1))
        tot = cnt+1
print(tot)

Solution (Python):

h,w = map(int,input().split())
n=[]
a=[]
a.append(["&"]*(w+2))
for i in range(h):
    arrc = list(input())
    arrc = ["&"]+arrc+["&"]
    b = arrc
    for j in range(len(arrc)):
        if b[j] == "
            n.append((i+1,j))
    a.append(b)
a.append(["&"]*(w+2))



p=[[1,0],[0,1],[-1,0],[0,-1]]

cnt=-1

while n:
    cnt +=1
    n2=[]
    
    for i,j in n:
        for di,dj in p:
            di +=i
            dj +=j
            if a[di][dj]==".":
                a[di][dj]="
                n2.append((di,dj))
    n=n2
print(cnt)

Solution (Python):
from sys import stdin
import sys
import collections



def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

def main():
    H, W = rip()
    S = [rs() for i in range(H)]
    
    min = [[-1] * W for i in range(H)]
    q = collections.deque()
    def enc(h, w): return h * W + w
    def inRange(t, l, r): return l <= t and t < r
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '
                q.append(enc(i,j))
                min[i][j] = 0
    while(len(q) > 0):
        rc = q.popleft()
        y = rc // W
        x = rc % W
        for t in range(4):
            nx = x + dx[t]
            ny = y + dy[t]
            if (not inRange(nx,0,W)) or (not inRange(ny,0,H)): continue
            if min[ny][nx] == -1:
                min[ny][nx] = min[y][x] + 1
                q.append(enc(ny,nx))
    
    ma = 0
    for i in range(H):
        for j in range(W):
            ma = max(ma, min[i][j])
    print(ma)





if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

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

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

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

print(int(ans))

Solution (Python):
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  M = [['

  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])

  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not M[bi - 1][bj]:
        M[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not M[bi][bj - 1]:
        M[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not M[bi + 1][bj]:
        M[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not M[bi][bj + 1]:
        M[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
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "
 
 
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)

if __name__ == "__main__":
    main()

Solution (Python):


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


def dfs(h,w):
    A[h][w]="
    que=[]
    if h>0:
        if A[h-1][w]!="
            que.append([h-1,w])
            A[h-1][w]="
    if w>0:
        if A[h][w-1]!="
            que.append([h,w-1])
            A[h][w-1]="
    if h<H-1:
        if A[h+1][w]!="
            que.append([h+1,w])
            A[h+1][w]="
    if w<W-1:
        if A[h][w+1]!="
            que.append([h,w+1])
            A[h][w+1]="
    
    return que


A=[]
for _ in range(H):
    A.append(list(input()))



ans=0
lis=[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="
            lis.append([h,w])
while True:
    pre=[]
    if lis:
        N=len(lis)
        lis=lis[::-1]
        for i in range(N):
            item=lis.pop(-1)
            pre+=dfs(item[0],item[1])
        lis=pre
    if len(lis)==0:
        break
    ans+=1
    
    
    
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):
from collections import deque

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

check = [[-1 for _ in range(W)] for _ in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if  A[i][j] == "
      check[i][j] = 0
      q.append((i, j))

while q:
  i, j = q.popleft()
  
  if i - 1 >= 0 and check[i - 1][j] == -1:
      check[i - 1][j] = check[i][j] + 1
      q.append((i - 1, j))

  if i + 1 < H and check[i + 1][j] == -1:
      check[i + 1][j] = check[i][j] + 1
      q.append((i + 1, j))

  if j - 1 >= 0 and check[i][j - 1] == -1:
      check[i][j - 1] = check[i][j] + 1
      q.append((i, j - 1))

  if j + 1 < W and check[i][j + 1] == -1:
      check[i][j + 1] = check[i][j] + 1
      q.append((i, j + 1))

answer = -1
for i in range(H):
  answer = max(answer, max(check[i]))
print(answer)

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

from collections import deque

def main():
  h,w=map(int,input().split())
  
  mp=[list(input()) for _ in range(h)]
  
  dist=[[-1]*w for i in range(h)]
  q=deque([])
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="
        dist[i][j]=0
        q.append([i,j])
      else:
        dist[i][j]=-1
  
  while q:
    x,y=q.popleft()
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx][yy]==-1):
        dist[xx][yy]=dist[x][y]+1
        q.append([xx,yy])
  
  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i][j])
      
  print(ret)
  return

main()


"""))

Solution (Python):


from collections import deque

def main():
  h,w=map(int,input().split())
  
  mp=[list(input()) for _ in range(h)]
  
  dist=[[-1]*w for i in range(h)]
  q=deque([])
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="
        dist[i][j]=0
        q.append([i,j])
      else:
        dist[i][j]=-1
  
  while q:
    x,y=q.popleft()
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx][yy]==-1):
        dist[xx][yy]=dist[x][y]+1
        q.append([xx,yy])
  
  ret=0
  for i in range(h):
    for j in range(w):
      ret=max(ret,dist[i][j])
      
  print(ret)
  return

main()

Solution (Python):
from collections import deque

def main():
  h,w=map(int,input().split())
  mp=[input() for _ in range(h)]
  dist=[-1]*(h*w)
  q=deque()
  
  for i in range(h):
    for j in range(w):
      if mp[i][j]=="
        q.append(i*w+j)
        dist[i*w+j]=0
      else:
        dist[i*w+j]=-1
  
 
  while q:
    c=q.popleft()
    
    x=c//w
    y=c%w
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      if (0<=xx<h and 0<=yy<w and dist[xx*w+yy]==-1):
        dist[xx*w+yy]=dist[x*w+y]+1
        q.append(xx*w+yy)
      
  print(max(dist))
  return

main()

Solution (Python):



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

    used = [True]*(h*w)

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


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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    H,W = map(int,input().split())

    
    visited = [[True]*(W+2)]
    visited += [[True] + [x == '
    visited.append([True]*(W+2))

    
    q = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if visited[i][j]:
                q.append((i,j))

    
    
    ans = -1
    while q:
        qq = []
        
        for x,y in q:
            if not visited[x-1][y]:
                visited[x-1][y] = True
                qq.append((x-1,y))
            if not visited[x+1][y]:
                visited[x+1][y] = True
                qq.append((x+1,y))
            if not visited[x][y-1]:
                visited[x][y-1] = True
                qq.append((x,y-1))
            if not visited[x][y+1]:
                visited[x][y+1] = True
                qq.append((x,y+1))
        q = qq
        ans += 1
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

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

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

Solution (Python):
import sys
import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

H, W = rl()
A = [list(rs()) for _ in range(H)]

INF = 10 ** 5
B = np.array([[0 if x == '

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

print(B.max())

Solution (Python):
import sys
from collections import deque

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

H, W = rl()
A = [list(rs()) for _ in range(H)]
answer = 0
que = deque()
data = [[-1] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            data[i][j] = 0
            que.append((j, i))
while que:
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        if 0 <= ny <= H-1 and 0 <= nx <= W-1:
            if data[ny][nx] == -1:
                data[ny][nx] = data[p[1]][p[0]] + 1
                que.append((nx, ny))
answer = max([max(z) for z in data])
print(answer)

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

import numpy as np

H,W = map(int,readline().split())
INF = 10 ** 9
A = INF * (np.frombuffer(read(),'S1').reshape(H,-1)[:,:W] == b'.')

for _ in range(4):
    
    A = A.T[:,::-1]
    N = A.shape[0]
    for i in range(1,N):
        A[i] = np.minimum(A[i-1] + 1, A[i])

answer = A.max()
print(answer)

Solution (Python):

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

buf = []

n = 0
for i in range(H):
    for j in range(W):
        if table[i][j] == '
            buf.append((i, j))
            n += 1


ans = 0
while n != H * W:
    ans += 1

    buf2 = []
    for i, j in buf:
        if i-1 >= 0 and table[i-1][j] != '
            table[i - 1][j] = '
            buf2.append((i-1, j))
            n += 1

        if i+1 < H and table[i+1][j] != '
            table[i + 1][j] = '
            buf2.append((i+1, j))
            n += 1

        if j-1 >= 0 and table[i][j-1] != '
            table[i][j-1] = '
            buf2.append((i, j-1))
            n += 1

        if j+1 < W and table[i][j+1] != '
            table[i][j+1] = '
            buf2.append((i, j+1))
            n += 1

    buf = buf2

    
    
    
    


print(ans)

Solution (Python):

import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(max(answer-1,0))
    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    A=[[] for _ in range(H+2)]
    A[0]=A[H+1]=['
    black=[]
    for i in range(1,H+1):
        row=list(input())
        A[i]=['
        for j,cell in enumerate(row):
            if cell=='
                black.append([i,j+1])
    nextcells=[]
    nextcells.extend(black)
    c=-1
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    while nextcells:
        c+=1
        cells=[]
        cells.extend(nextcells)
        nextcells=[]
        for cell in cells:
            for k in range(4):
                if A[cell[0]+dy[k]][cell[1]+dx[k]]=='.':
                    nextcells.append([cell[0]+dy[k],cell[1]+dx[k]])
                    A[cell[0]+dy[k]][cell[1]+dx[k]]='
    print(c)
        

if __name__ == '__main__':
    main()

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

MAP=[["." for i in range (W)]for i in range(H)]
LIST=[0]*(10**6+100)

l=0
r=0
for i in range(H):
    A=list(input())
    for j in range(W):
        if(A[j]=="
            MAP[i][j]="
            LIST[r]=(i,j,0)
            r+=1

while(True):
    T=LIST[l]
    i=T[0]
    j=T[1]
    if(i>0):
        if(MAP[i-1][j]=="."):
            MAP[i-1][j]="
            LIST[r]=(i-1,j,T[2]+1)
            r+=1  
    if(i+1<H):
        if(MAP[i+1][j]=="."):
            MAP[i+1][j]="
            LIST[r]=(i+1,j,T[2]+1)
            r+=1  
    if(j>0):
        if(MAP[i][j-1]=="."):
            MAP[i][j-1]="
            LIST[r]=(i,j-1,T[2]+1)
            r+=1  
    if(j+1<W):
        if(MAP[i][j+1]=="."):
            MAP[i][j+1]="
            LIST[r]=(i,j+1,T[2]+1)
            r+=1
    l+=1
    if(r<=l):
        print(LIST[r-1][2])
        exit()

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    grid = [['' for _ in range(W)] for _ in range(H)]
    que = deque()
    for i in range(H):
        grid[i] = list(input())
        for j in range(W):
            if grid[i][j] == '
                que.append([i, j])
    
    xy = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    ans = 0
    while que:
        n = len(que)
        for _ in range(n):
            y, x = que.popleft()
            for i in range(4):
                xi = x - xy[i][0]
                yi = y - xy[i][1]
                if 0 <= xi <= W-1 and 0 <= yi <= H-1:
                    if grid[yi][xi] == '.':
                        grid[yi][xi] = '
                        que.append([yi, xi])
        ans += 1
    print(ans-1)


if __name__ == '__main__':
    solve()