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=list(map(int,input().split()))
inf=float("inf")
import numpy as np
mem=np.full((H,W),inf)
l=[list(input()) for i in range(H)]
for i in range(H):
   for j in range(W):
      if l[i][j]=="
         mem[i,j]=0
for i in range(W-1):
   mem[:,i+1]=np.minimum(mem[:,i]+1,mem[:,i+1])
for i in reversed(range(1,W)):
   mem[:,i-1]=np.minimum(mem[:,i-1],mem[:,i]+1)
for i in range(H-1):
   mem[i+1,:]=np.minimum(mem[i+1,:],mem[i,:]+1)
for i in reversed(range(1,H)):
   mem[i-1,:]=np.minimum(mem[i-1,:],mem[i,:]+1)
print(int(np.max(mem)))

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):
h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != h-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))

Solution (Python):


import collections

def main():
    H, W = input_list()
    grid = [input() for i in range(H)]
    dist = [[-1]*W for _ in range(H)]
    black_cells = collections.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):
        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
    
    print(bfs(black_cells, dist))
    



def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

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


def bfs(H, W, black_cells, dist):
    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


def main():
    H, W = map(int, input().split())
    grid = [input() for _ 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
    print(bfs(H, W, black_cells, dist))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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


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

Q=deque()

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


while Q:
  x,y,z=Q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.':
      Q.append((nx,ny,z+1))
      maze[nx][ny]='


print(z)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    h,w = map(int,ipt().split())
    dq = deque()
    a = [input()+"
    d = [[-1]*(w+1) for i in range(h+1)]
    for i in range(h):
        d[i][w] = 0
    for i in range(w):
        d[h][i] = 0

    for i in range(h):
        ai = a[i]
        for j in range(w):
            if ai[j] == "
                d[i][j] = 0
                for dx,dy in dir:
                    nx = i+dx
                    ny = j+dy
                    if a[nx][ny] == "." and d[nx][ny] == -1:
                        dq.append((nx,ny))
                        d[nx][ny] = 1

    while dq:
        qx,qy = dq.popleft()
        nd = d[qx][qy]
        for dx,dy in dir:
            nx = qx+dx
            ny = qy+dy
            if a[nx][ny] == "." and d[nx][ny] == -1:
                dq.append((nx,ny))
                d[nx][ny] = nd+1


    ma = 0
    for i in d:
        for j in i:
            if ma < j:
                ma = j

    print(ma)




    return None

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

q = deque()

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

while q:
    y, x, d = q.popleft()
    if a[y][x] == '
        for xdx, ydy in zip((x, x, x+1, x-1), (y+1, y-1, y, y)):
            if (0 <= xdx < w) and (0 <= ydy < h):
                if a[ydy][xdx] == '.':
                    a[ydy][xdx] = '
                    q.append((ydy, xdx, d+1))
print(d)

Solution (Python):
from collections import deque

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

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

def bfs(q, v, c):
    while q:
        y, x = q.popleft()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                c[ny][nx] = c[y][x] + 1
                v[ny][nx] = 1
                q.append([ny, nx])

bfs(queue, visited, cnt)

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

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class TwoDimGrid:
    
    def __init__(self, h, w, wall="o"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]


        d = deque()
        for i in range(1, self.h+1):
            for j in range(1, self.w+1):
                if self.getgrid(j, i) == "
                    self.set(j, i, 0)
                    d.append((j, i, 0))
        
        ans = 0
        while d:
            
            cx, cy, cc = d.popleft()
            for dx, dy in move:
                nx, ny = dx + cx, dy + cy
                
                if self.getgrid(nx, ny) == ".":

                    if self.get(nx, ny) > cc + 1:
                        ans = max(ans, cc + 1)
                        self.set(nx, ny, cc + 1)
                        d.append((nx, ny, cc + 1))

        
        print(ans)



def solve():
    h, w = getList()
    g = TwoDimGrid(h, w)
    g.search()
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)]

from collections import deque


queue = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            queue.append([i, j, 0])
            seen[i][j] = 0

def bfs(maze, seen):
    while queue:
        y, x, c = queue.popleft()
        for i, j in [1, 0], [-1, 0], [0, 1], [0, -1]:
            dy = y + i
            dx = x + j
            if dy < 0 or H <= dy or dx < 0 or W <= dx:
                continue
            if seen[dy][dx] > -1:
                continue
            if maze[dy][dx] == '
                continue
            seen[dy][dx] = c + 1
            queue.append([dy, dx, c+1])

def check_max(seen):
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, seen[i][j])
    return ans
    
bfs(maze, seen)
print(check_max(seen))

Solution (Python):
from collections import deque

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

ds = [[-1,0],[1,0],[0,-1],[0,1]]
q = deque([])

cnt = 0

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

if cnt == H*W:
  print(0)
  exit()

while q:
  t = q.popleft()
  for d in ds:
    ny = t[0]+d[0]
    nx = t[1]+d[1]
    if 0 <= ny < H and 0<= nx < W:
      if mp[ny][nx] == '.':
        mp[ny][nx] = '
        q.append((ny,nx,t[2]+1))
        cnt += 1
        if cnt == H*W:
          print(t[2]+1)
          exit()

Solution (Python):
from collections import deque

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

for i in range(1,H+1):
    A[i]="*"+input()+"*"

inf=float("inf")
Dist=[[inf]*(W+2) for _ in range(H+2)]
Q=deque()

for x in range(1,H+1):
    for y in range(1,W+1):
        if A[x][y]=="
            Dist[x][y]=0
            Q.append((x,y))

E=[(-1,0),(1,0),(0,-1),(0,1)]
while Q:
    (x,y)=Q.popleft()
    for (a,b) in E:
        if A[x+a][y+b]=="." and Dist[x+a][y+b]==inf:
            Dist[x+a][y+b]=Dist[x][y]+1
            Q.append((x+a,y+b))

Ans=0
for x in range(1,H+1):
    for y in range(1,W+1):
        Ans=max(Ans,Dist[x][y])
print(Ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "
            queue.append([i, j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while queue:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] + 1
            queue.append([nh, nw])
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 main():
    h, w = map(int,input().split())
    A = [list(input()) for _ in range(h)]
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()

Solution (Python):
from collections import deque


def bfs(S):  
    dist = [[-1] * w for _ in range(h)]  
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return max(max(ans) for ans in dist)


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

Solution (Python):
from collections import deque


def bfs(S):  
    dist = [-1] * (w * h)  
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '
                dist[j + (w * i)] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  
            if 0 <= i < h and 0 <= j < w and dist[j + (w * i)] < 0:
                dist[j + (w * i)] = dist[y + (w * x)] + 1
                que.append((i, j))
    return max(dist)


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

Solution (Python):
from collections import deque


def bfs(S):  
    dist = [[-1] * w for _ in range(h)]  
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


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

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

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

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

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

while True:
    nl = []
    
    for x, y in l:
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and A[nx][ny]=='.':
                nl.append((nx, ny))
                A[nx][ny] = '
    
    if len(nl)==0:
        break
    
    l = nl
    ans += 1

print(ans)

Solution (Python):
import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

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

    que = deque()
    for x in range(W):
        for y in range(H):
            if A[y][x] == '
                que.append((x,y,0))        
    ans = 0
    while que:
        x,y,c = que.popleft()
        for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
            sx = x + dx
            sy = y + dy
            if sx < 0 or sx >= W or sy < 0 or sy >= H or A[sy][sx] == '
                continue
            if A[sy][sx] == '.':
                que.append((sx,sy,c+1))
                A[sy][sx] = c + 1
                ans = max(ans,c+1)
    print(ans)

if __name__ == "__main__":
    main()

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

from collections import deque
q = deque()
reach = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='
            q.append([i,j,0])
            reach[i][j] = True

ans = 0
while q:
    i,j,cnt = q.popleft()
    ans = max(ans,cnt)
    for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=i+k<h and 0<=j+l<w:
            if not reach[i+k][j+l]:
                q.append([i+k,j+l,cnt+1])
                reach[i+k][j+l] = True

print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    A = [SS() for _ in range(H)]

    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    dist = [[INF] * W for i in range(H)]
    que = collections.deque()

    for i, j in itertools.product(range(H), range(W)):
        if A[i][j] == '
            que.append((i, j))
            dist[i][j] = 0

    while que:
        cy, cx = que.popleft()
        for dy, dx in d:
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < H and 0 <= nx < W and dist[cy][cx] + 1 < dist[ny][nx]:
                dist[ny][nx] = dist[cy][cx] + 1
                que.append((ny, nx))

    
    

    ans = max([max(i) for i in dist])
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
dp=[[-1]*w for i in range(h)]
Q=deque([])
for i in range(h):
    s=SI()
    for j in range(w):
        if s[j]=="
            dp[i][j]=0
            Q.append((i,j))
step=[(-1,0),(1,0),(0,1),(0,-1)]
while Q:
    x,y=Q.popleft()
    for i,j in step:
        if not(0<=x+i<h and 0<=y+j<w):
            continue
        if dp[x+i][y+j]<0:
            Q.append((x+i,y+j))
            dp[x+i][y+j]=dp[x][y]+1
ans=-inf

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

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    d = [[float('inf')] * W for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                d[h][w] = 0
                Q.append([h,w])
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    while Q:
        h,w = Q.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if A[nh][nw] == '.' and d[nh][nw] == float('inf'):
                    A[nh][nw] = '
                    d[nh][nw] = min(d[nh][nw], d[h][w] + 1)
                    Q.append([nh,nw])

    ans = 0
    for h in range(H):
        ans = max(ans, max(d[h]))

    print(ans)
    


if __name__ == "__main__":
    main()

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

from collections import deque

visited = [[False] * w for _ in range(h)]

q = deque()
for i in range(h):
    for j in range(w):
        if A[i][j] == '
            q.append((i, j, 0))
            visited[i][j] = True

cnt = 0
while q:
    y, x, count = q.popleft()
    cnt = max(cnt, count)
    for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
        if visited[ny][nx]: continue
        q.append((ny, nx, count + 1))
        visited[ny][nx] = True
print(cnt)

Solution (Python):
from collections import deque
inf=float("inf")

def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    for i in range(h):
        for j in range(w):
            if A[i][j]=="
                queue.append([i,j])
                color[i][j]="black"
                D[i][j]=0

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    color[X][Y]="gray"
                    D[X][Y]=D[x][y]+1
                    queue.append([X,Y])
        color[x][y]="black"

    return D


h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
D=BFS()
ans=0
for i in range(h):
    ans=max(ans,max(D[i]))
print(ans)

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

INF = 10**18

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

q = deque([])
dist = [[INF for _ in range(W)]for _ in range(H)]
for y, A_line in enumerate(A):
    for x, a in enumerate(A_line):
        if a == "
            dist[y][x] = 0
            q.append((x, y))

while q:
    t_pos = tx, ty = q.popleft()
    dist_t = dist[ty][tx]

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        elif A[y][x] == "
            continue
        elif dist[y][x] <= dist_t + 1:
            continue
        dist[y][x] = dist_t + 1
        q.append(pos)


r = max(chain(*dist))
print(r)

Solution (Python):
from collections import deque
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    B = [(i, j) for i, a in enumerate(A) for j, b in enumerate(a) if b == '
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = deque(B)
    colored = len(B)
    tot = h * w
    count = 0
    while colored < tot:
        next = deque([])
        while stack:
            y, x = stack.popleft()
            for dx, dy in dxy:
                X = x + dx
                Y = y + dy
                if X < 0 or X >= w or Y < 0 or Y >= h:
                    continue
                if A[Y][X] == '.':
                    next.append((Y, X))
                    A[Y][X] = '
        stack = next
        count += 1
        colored += len(next)
    print(count)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque
H, W = map(int, input().split())
map = [list(input()) for i in range(H)]
checked = list()
queue = deque()
for x in range(H):
    checked.append(list())
    for y in range(W):
        if map[x][y]=="
            checked[x].append(True)
            queue.append((x, y, 0))
        else:
            checked[x].append(False)
neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
while queue:
    x, y, res = queue.popleft()
    for dx, dy in neighbors:
        nx, ny = x+dx, y+dy
        if 0<=nx<H and 0<=ny<W:
            if not checked[nx][ny]:
                queue.append((nx, ny, res+1))
                checked[nx][ny] = True
print(res)

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







def search():
    H, W = map(int, input().split()) 
    pos = deque([])

    D = [[True] * (W + 2)]  
    D += [[True] + [False] * W + [True] for i in range(H)]  
    D.append([True] * (W + 2))  
    
    
    
    
    

    for i in range(H):
        maze = input() 
        for j in range(W):
            if maze[j] == "
                pos.append([i + 1, j + 1, 0]) 
                D[i + 1][j + 1] = True
    
    
    
    
    

    while len(pos) > 0:
        h, w, depth = pos.popleft()
        

        if not D[h + 1][w]: 
            pos.append([h + 1, w, depth + 1]) 
                                              
            D[h + 1][w] = True 

        if not D[h - 1][w]:
            pos.append([h - 1, w, depth + 1])
            D[h - 1][w] = True

        if not D[h][w + 1]:
            pos.append([h, w + 1, depth + 1])
            D[h][w + 1] = True

        if not D[h][w - 1]:
            pos.append([h, w - 1, depth + 1])
            D[h][w - 1] = True
    
    return depth


print(search())

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
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    R,C = NMI()
    
    
    board = [list(input()) for _ in range(R)]
    
    ans = 0

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

    
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

    
    que = deque([])
    
    
    for r in range(R):
        for c in range(C):
            if board[r][c] == '
                que.append((r,c))
                
                distance[r][c] = 0

                
    cnt = 0
    
    
    while len(que) != 0:
        
        pop = que.popleft()
        
        
        for i in range(len(dx)):
            
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            
            if 0<= ny < R and 0 <= nx < C and distance[ny][nx] == INF:
                
                que.append((ny,nx))
                
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
                if ans < distance[ny][nx]:
                    ans = distance[ny][nx]
                
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
H,W = map(int,input().split())
grid = []
d = deque()
next_d = deque()
for i in range(H):
    grid.append(list(input()))
for i in range(H):
    for j in range(W):
        if grid[i][j] == '
            d.append((i,j))
dx = [0,-1,0,1]
dy = [1,0,-1,0]
ans = -1
while d:
    ans += 1
    while d:
        y,x = d.pop()
        for i in range(4):
            next_y = y+dy[i]
            next_x = x+dx[i]
            if next_y >= 0 and next_y < H and next_x >= 0 and next_x < W:
                if grid[next_y][next_x] == '.':
                    grid[next_y][next_x] = '
                    next_d.append((next_y,next_x))
    d = next_d
    next_d = deque()
print(ans)

Solution (Python):
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["
for _ in range(H):
    grid.append(list("
grid.append(["


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

ans = 0
while q:
    x, y, count = q.popleft()
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[y+dy][x+dx] != ".":
            continue
        grid[y+dy][x+dx] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))


print(ans)

Solution (Python):
import sys 
from collections import deque
 
h, w = map(int, sys.stdin.readline().split())
grid = []
for _ in range(h):
    grid.append(list(sys.stdin.readline().strip()))
 
q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "
            q.append((0, i, j))
 
while q:
    count, y, x = q.popleft()
    for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        if 0 <= y+dy < h and 0 <= x+dx < w:
            if grid[y+dy][x+dx] == "
                continue
            else:
                grid[y+dy][x+dx] = "
                q.append((count+1, y+dy, x+dx))
 
print(count)