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):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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 power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [list(sr()) for i in range(h)]
ans = 0
q = deque([])
visited = [[False for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            q.append([i,j])
dir = [[1,0], [-1,0], [0,1], [0,-1]]
while q:
    neq = deque([])
    while q:
        y,x = q.popleft()
        for dy,dx in dir:
            ny,nx = y+dy,x+dx
            if 0<=ny<h and 0<=nx<w and (not visited[ny][nx]) and a[ny][nx] == '.':
                neq.append([ny,nx])
                visited[ny][nx]  = True
                a[ny][nx] = '
    if neq:
        ans+=1
        q = neq
    else:
        break
print(ans)

Solution (Python):
from collections import deque

H,W = map(int,input().split())
maze = list(list(input()) for i in range(H))
maze_s = [[-1] * W for i in range(H)]
queue = deque([])
for i,row in enumerate(maze):
  for j,value in enumerate(row):
    if value == "
      queue.append([i, j])
      maze_s[i][j] = 0
def bfs(maze, maze_s):
  while queue:
    y,x = queue.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
      new_y,new_x= y+i,x+j
      if 0 <= new_y <= H-1 and 0<= new_x <= W-1:
        if maze[new_y][new_x] == "." and maze_s[new_y][new_x] == -1:
          maze_s[new_y][new_x] = maze_s[y][x] + 1
          queue.append([new_y,new_x])
  c = 0
  for row in maze_s:
    m = max(row)
    c = max(c,m)
  print(c)

bfs(maze,maze_s)

Solution (Python):


from collections import deque
h, w = map(int, input().split())

matrix = []
for _ in range(h):
    matrix.append(list(input()))

def bfs(matrix):
    
    dy = [-1, 0, 1, 0]
    dx = [0, 1, 0, -1]
    q = deque()
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == '
                q.append((i, j))
    ans = 0
    next_q = deque()
    while q:
        y, x = q.popleft()
        for i in range(4):
            next_y = dy[i] + y
            next_x = dx[i] + x
            if 0 <= next_y < h and 0 <= next_x < w and matrix[next_y][next_x] == '.':
                matrix[next_y][next_x] = '
                next_q.append((next_y, next_x))
        if not q and next_q:
            q = next_q
            next_q = deque()
            ans += 1
    return ans

ans = bfs(matrix)
print(ans)

Solution (Python):
H,W = map(int,input().split())
lis = [[1000000007] * W for i in range(H)]
A = []
for i in range(H):
    Ain = list(input())
    A.append(Ain)
    for j in range(W):
        if A[i][j] == '
            lis[i][j] = 0
        else:
            lis[i][j] = min(lis[i][j],lis[i][j-1]+1)

    for j in reversed(range(W-1)):
        lis[i][j] = min(lis[i][j],lis[i][j+1]+1)


for j in range(W):
    for i in range(1,H):
        lis[i][j] = min(lis[i][j],lis[i-1][j]+1)
    for i in reversed(range(H-1)):
        lis[i][j] = min(lis[i][j],lis[i+1][j]+1)


ans = 0
for i in range(H):
    ans = max(ans,max(lis[i]))
print(ans)

Solution (Python):
from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
print(ans)

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

Solution (Python):
h,w=map(int,input().split())
a=[input() for _ in range(h)]
visited=[[0]*w for _ in range(h)]
from collections import deque
q=deque([])
for i in range(h):
  for j in range(w):
    if a[i][j]=="
      q.append((i,j,0))
      visited[i][j]=1
ans=0
while q:
  i,j,count=q.popleft()
  ans=max(ans,count)
  for nxi,nxj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
    if 0<=nxi<h and 0<=nxj<w and visited[nxi][nxj]==0:
      visited[nxi][nxj]=1
      q.append((nxi,nxj,count+1))
print(ans)

Solution (Python):
import sys


input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



class queue:
	def __init__(self):
		self.l=[0]*(1000*1000+100)
		self.f=0
		self.t=0
		
	def put(self,v):
		self.l[self.f]=v
		self.f+=1
		
	def get(self):
		self.t+=1
		return self.l[self.t-1]
		
	def empty(self):
		return self.f==self.t

def main():
	
	h, w = tin()
	
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '
				dist[hi][wi]=0
				open_list.put(hi*2000+wi)
				
	max_dist=0
	while not open_list.empty():
		hi_wi = open_list.get()
		hi = hi_wi // 2000
		wi = hi_wi % 2000
		d = dist[hi][wi]
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			
				
			dist[hi+dh][wi+dw]=d+1
			open_list.put(((hi+dh)*2000+wi+dw))
			max_dist=d+1
	print(max_dist)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


import itertools
import collections





def main():
    h, w = input_list()
    grids = [list(input()) for i in range(h)]
    dist = [[-1]*w for _ in range(h)]

    black_cells = collections.deque()
    for hi in range(h):
        for wi in range(w):
            if grids[hi][wi] == '
                black_cells.append((hi, wi))
                dist[hi][wi] = 0

    print(bfs(h, w, black_cells, dist))


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 input_list():
    return list(map(int, input().split()))


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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
 
 
 
print(ans)

Solution (Python):
def main():
    INF = 10 ** 6
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    d = [[INF for _ in range(W)] for _ in range(H)]
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                d[h][w] = 0
    
    for h in range(H):
        
        for w in range(1, W):
            d[h][w] = min(d[h][w], 1 + d[h][w - 1])
        
        for w in range(W - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h][w + 1])
    
    for w in range(W):
        for h in range(1, H):
            d[h][w] = min(d[h][w], 1 + d[h - 1][w])
        for h in range(H - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h + 1][w])
    
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, d[h][w])
    print(ans)


if __name__ == '__main__':
    main()

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs_grid(H, W, s, grid):

    q = deque(s)
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    ans = 0

    while True:

        nq = deque()
        f = False
        while q:
            now = q.popleft()
            x, y = now
            for m in move:
                nx, ny = x + m[0], y + m[1]
                if 0 <= nx < W and 0 <= ny < H:
                    if grid[ny][nx]:
                        f = True
                        grid[ny][nx] = False
                        nq.append((nx, ny))

        if f:
            ans += 1
        if nq:
            q = nq
        else:
            break

    return ans


def main():

    H, W = in_nn()
    grid = in_map2(H)

    s = []
    for y in range(H):
        for x in range(W):
            if not grid[y][x]:
                s.append((x, y))

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

    print(bfs_grid(H, W, s, grid))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
H,W=map(int,input().split())
maze=[]
visited=[[None]*W for _ in range(H)]
q=deque([])
for i in range(H):
    a=input().rstrip()
    maze.append(a)
    for j in range(W):
        if a[j]=="
            visited[i][j]=0
            q.append([i,j])
ans=0
while q:
    h,w=q.popleft()
    for nh,nw in ([h+1,w],[h-1,w],[h,w+1],[h,w-1]):
        if nh<0 or nh>H-1 or nw<0 or nw>W-1:
            continue
        if visited[nh][nw]!=None:
            continue
        visited[nh][nw]=visited[h][w]+1
        ans=max(ans,visited[nh][nw])
        q.append([nh,nw])
print(ans)

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

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().split()))

def pad(mxy, wall="
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

vD = [(0,1),(1,0),(0,-1),(-1,0)]
vQ = deque([])
vQ_app, vQ_popl = vQ.append, vQ.popleft

def main():
	H,W = linput()
	mM = [input().rstrip() for _ in [0,]*H]
	mM = pad(mM,"$")
	
	res = 0
	cnt = 0
	
	mV = [[INF,]*(W+2) for _ in [INF,]*(H+2)]
	for sr in range(1,H+1):
		for sc in range(1,W+1):
			if mM[sr][sc]==".":
				continue
			mV[sr][sc] = 0
			vQ_app((sr,sc))
	
	while vQ:
		r,c = vQ_popl()
		now_cost = mV[r][c]
		for dr,dc in vD:
			nr,nc = r+dr, c+dc
			if mM[nr][nc]=="$":
				continue
			if now_cost + 1 < mV[nr][nc]:
				vQ_app((nr,nc))
				mV[nr][nc] = now_cost + 1
				res = max(now_cost+1, res)
		
		cnt += 1
		
		if cnt>4999999: break
	
	print(res)

if __name__ == "__main__":
	main()

Solution (Python):








import itertools
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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


q = []

for i in range(H):
    for j in range(W):
        if Board[i][j] == '
            
            q.append((i, j))

ans = 0

for i in itertools.count():
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                
                Board[y][x] = '
                qq.append((y, x))
    q = qq
    if not q:
        break




print(ans-1)

Solution (Python):









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

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


q = []

for i in range(H):
    for j in range(W):
        if Board[i][j] == '
            
            q.append((i, j))

ans = 0
while q:
    qq = []
    ans += 1
    for yx in q:
        for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            y = yx[0] + d[0]
            x = yx[1] + d[1]
            
            if y < 0 or H - 1 < y or x < 0 or W - 1 < x:
                pass
            elif Board[y][x] == '.':
                
                Board[y][x] = '
                qq.append((y, x))
    q = qq




print(ans-1)

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
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

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = deque() 

    for h in range(H):
        for w in range(W):
            if F[h][w] == "
                Q.append((h, w, 0))
                A[h * W + w] = True

    res = V(max)
    while Q:
        h, w, d = Q.popleft()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * W + ww]:
                    continue
                Q.append((hh, ww, d + 1))
                A[hh * W + ww] = True
    
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                queue.append(W*i + j)
                visit[W*i + j] = 0
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    print(max(visit))

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    visited = [[float('inf')] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                Q.append((h,w))
                visited[h][w] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    while Q:
        y, x = Q.popleft()
        now = visited[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == float('inf'):
                    visited[ny][nx] = now + 1
                    Q.append((ny,nx))
                    ans = max(ans, now + 1)

    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def bfs(que,d): 
  
  
  
  
  
  
  
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        
        continue
      if d[ny][nx]==float("inf"):
        d[ny][nx] = lead + 1
        que.append((ny,nx))
  return lead

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


d = [[float("inf")] * 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))
      
      d[i][j] = 0


lead = bfs(que,d)
print(lead)

Solution (Python):
from collections import deque

def bfs(que,d): 
  
  
  
  lead = 0
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  
  
  
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        continue
      if d[ny][nx]==float("inf"):
        d[ny][nx] = lead + 1
        que.append((ny,nx))
  return lead

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

d = [[float("inf")] * 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))
      d[i][j] = 0


lead = bfs(que,d)
print(lead)

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):
    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):
H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
cnt = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '
      pos.append([i, j])
      A[i][j] = 1
      cnt += 1
ccnt = 0
pnt = 0
while pnt < cnt:
  n = cnt
  ccnt += 1
  for i in range(pnt, cnt):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
        cnt += 1
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
        cnt += 1
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
        cnt += 1
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
        cnt += 1
  pnt = n
print(ccnt-1)

Solution (Python):
H, W = map(int, input().split())
S = [input() for i in range(H)]
A = [[0 for j in range(W)] for i in range(H)]
pos = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '
      pos.append([i, j])
      A[i][j] = 1
cnt = 0
while pos != []:
  n = len(pos)
  cnt += 1
  for i in range(n):
    x, y = pos[i][0], pos[i][1]
    if x > 0:
      if A[x-1][y] == 0:
        A[x-1][y] = 1
        pos.append([x-1, y])
    if x < H-1:
      if A[x+1][y] == 0:
        A[x+1][y] = 1
        pos.append([x+1, y])
    if y > 0:
      if A[x][y-1] == 0:
        A[x][y-1] = 1
        pos.append([x, y-1])
    if y < W-1:
      if A[x][y+1] == 0:
        A[x][y+1] = 1
        pos.append([x, y+1])
  pos = pos[n:]
print(cnt-1)

Solution (Python):

import sys
from collections import deque
def main(H, W, A):
    dist = [[-1] * W for _ in range(H)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                dist[i][j] = 0
                q.append((i, j, 0))

    ans = 0
    while q:
        i, j, d = q.popleft()
        ans = max(ans, d)
        for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if not (0 <= ni < H and 0 <= nj < W): continue
            if dist[ni][nj] >= 0: continue
            dist[ni][nj] = d + 1
            q.append((ni, nj, d + 1))
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().rstrip() for _ in range(H)]
    main(H, W, A)

Solution (Python):
from collections import deque
def start_search(G):
    start=[]
    for i in range(H):
        for j in range(W):
            if G[i][j]=='
                start.append((i,j))
    return start
def bfs(G,visited,start):
    queue=deque(start)
    cnt=0
    for p,q in start:
        visited[p][q]=0
    while queue:
        tmp=len(queue)
        for _ in range(tmp):
            (y,x)=queue.popleft()
            for j,k in ([1,0],[0,1],[-1,0],[0,-1]):
                tmp_y,tmp_x = y+j,x+k
                if 0<=tmp_y<=H-1 and 0<=tmp_x<=W-1 and visited[tmp_y][tmp_x]==-1:
                    visited[tmp_y][tmp_x]=visited[y][x]+1
                    queue.append([tmp_y,tmp_x])
        cnt+=1
    return cnt-1
if __name__=="__main__":
    H,W = map(int,input().split())
    G=[input() for _ in range(H)]
    start=start_search(G)
    visited=[[-1]*W for _ in range(H)]
    print(bfs(G,visited,start))

Solution (Python):
from collections import deque


def resolve():
    H, W = map(int, input().split())
    A, q = [], deque([])
    for i in range(H):
        A.append(list(input()))
        if '
            for j in range(W):
                if A[i][j] == '
                    q.append((i, j))

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

    
    nq = deque([])
    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 A[ny][nx] == '.':
                nq.append((ny, nx))
                A[ny][nx] = '
        if q == deque([]):
            q = nq
            nq = deque([])
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque



def bfs():
    
    d = [[float("inf")] * m for i in range(n)]

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

    
    que = deque([])
   
    for i in range(n):
        for j in range(m):
            
            if maze[i][j] == "
                sx = i
                sy = j
                que.append((sx, sy))
                d[sx][sy] = 0

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

            
            
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "
                
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    ans = 0
    for i in range(n):
        for j in range(m):
            ans = max(ans, d[i][j])
    
    return ans

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]

print(bfs())