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

Solution (Python):
from collections import deque 
import sys
input = sys.stdin.readline
q = deque([])
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
x=[[-1,0],[1,0],[0,-1],[0,1]]
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            for k in x:
                if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                    a[i+k[0]][j+k[1]]="0"
                    q.append([i+k[0],j+k[1],1])
ans=0
while q:
    v=q.popleft()
    for k in x:
        if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
            a[v[0]+k[0]][v[1]+k[1]]="0"
            q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
            ans=v[2]+1
print(ans)

Solution (Python):
from collections import deque 
import sys
input = sys.stdin.readline
def main():
    q = deque([])
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]="0"
                        q.append([i+k[0],j+k[1],1])
    ans=0
    while q:
        v=q.popleft()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]="0"
                q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()

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

A=[list('X'+input()+'X') for i in range(H)]
A.append('X'*(W+2))
A.insert(0,'X'*(W+2))
d=[[0,1],[0,-1],[1,0],[-1,0]]
wnum=0
blis=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]=='.':
            wnum+=1
        if A[i][j]=='
            blis.append([i,j])

if wnum==0:
    print(0)
    exit()

ans=0
wtob=0
while len(blis):
    ans+=1
    nblis=[]
    for p in blis:
        for v in d:
            ny=p[0]+v[0]
            nx=p[1]+v[1]
            if A[ny][nx]=='.':
                A[ny][nx]='
                nblis.append([ny,nx])
                wtob+=1
    if wtob==wnum:
        print(ans)
        exit()
    blis=[]
    for i in nblis:
        blis.append(i)

Solution (Python):

import numpy as np
h,w = list(map(int,input().split()))
S = [[x for x in input()] for _ in range(h)]

s = np.zeros((h,w), dtype='int')
for i in range(h):
  for j in range(w):
    if S[i][j] == '.':
      s[i,j] = h*w

def rev():
  for i in range(1,h):
    s[i,:] = np.minimum(s[i,:], s[i-1,:]+1)
  for i in range(h-1)[::-1]:
    s[i,:] = np.minimum(s[i,:], s[i+1,:]+1)
  for i in range(1,w):
    s[:,i] = np.minimum(s[:,i], s[:,i-1]+1)
  for i in range(w-1)[::-1]:
    s[:,i] = np.minimum(s[:,i], s[:,i+1]+1)

rev()
print(np.max(s))

Solution (Python):
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]
research_point = deque()



def search_min_step():
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue
            
            if Map[y_next][x_next] == '
                 min_step_map[y_next][x_next] <= min_step_map[y_now][x_now] + 1:
                continue
            else:
                min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '
            min_step_map[y][x] = 0
            research_point.append([y, x])

search_min_step()

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)

Solution (Python):

from collections import deque

H, W = map(int, input().split())
A = [input() for i in range(H)]
breadth = [[-1] * W for i in range(H)]
queue = deque()

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


def search(A, breadth):
    d = 0
    while queue:
        y, x = queue.popleft()
        d = breadth[y][x]
        for i, j in [-1, 0], [1, 0], [0, -1], [0, 1]:
            newy, newx = y + i, x + j
            if newy < 0 or newx < 0 or newy >= H or newx >= W:
                continue
            if breadth[newy][newx] == -1:
                breadth[newy][newx] = d + 1
                queue.append([newy, newx])

    return d


print(search(A, breadth))

Solution (Python):
from collections import deque

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

a = [[False] * (w + 2)]
for y in range(h):
    a.append([False] + [x != '
a.append([False] * (w + 2))

s = deque()
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if not a[i][j]:
            s.append((i, j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i - 1][j]:
            a[i - 1][j] = False
            ns.append((i - 1, j))
        if a[i + 1][j]:
            a[i + 1][j] = False
            ns.append((i + 1, j))
        if a[i][j - 1]:
            a[i][j - 1] = False
            ns.append((i, j - 1))
        if a[i][j + 1]:
            a[i][j + 1] = False
            ns.append((i, j + 1))

    s = ns
    ans += 1

print(ans)

Solution (Python):
from collections import deque


def main():
    height, width = map(int, input().split())
    grid = []
    q = deque([])
    change_time = [[float("inf") for _ in range(width)] for _ in range(height)]
    for i in range(height):
        now = list(input())
        for j in range(width):
            if now[j] == "
                q.append([i, j, 0])
                change_time[i][j] = 0
        grid.append(now)
    d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    answer = 0
    while q:
        y, x, time = q.popleft()
        for dy, dx in d:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                grid[new_y][new_x] = "
                change_time[new_y][new_x] = change_time[y][x] + 1
                q.append([new_y, new_x, change_time[new_y][new_x]])
                answer = max(answer, change_time[new_y][new_x])
    print(answer)


if __name__ == '__main__':
    main()

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


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [list(stdin.readline()) for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                distance[new_y][new_x] = answer + 1
                grid[new_y][new_x] = "
                q.append((new_y, new_x))
    print(answer)


if __name__ == '__main__':
    main()

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


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [stdin.readline() for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and distance[new_y][new_x] < 0:
                distance[new_y][new_x] = answer + 1
                q.append((new_y, new_x))
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[True] * 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] = False
cnt = -1
while q:
    cnt += 1
    qq = deque()
    for y, x in q:
        if x + 1 < w and dist[y][x + 1]:
            dist[y][x + 1] = False
            qq.append((y, x + 1))
        if x - 1 >= 0 and dist[y][x - 1]:
            dist[y][x - 1] = False
            qq.append((y, x - 1))
        if y + 1 < h and dist[y + 1][x]:
            dist[y + 1][x] = False
            qq.append((y + 1, x))
        if y - 1 >= 0 and dist[y - 1][x]:
            dist[y - 1][x] = False
            qq.append((y - 1, x))
    q = qq
print(cnt)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[False] * 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] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cnt = -1
while q:
    cnt += 1
    qq = []
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or dist[yy][xx]:
                continue
            else:
                dist[yy][xx] = True
                qq.append((yy, xx))
    q = qq
print(cnt)

Solution (Python):
import numpy as np

H,W = map(int,input().split())
maze = [list(input())for _ in range(H)]
for i in range(H):
  for j in range(W):
    if maze[i][j]=="
      maze[i][j]=0
    else:
      maze[i][j]=float('INF')
maze = np.array(maze)
      
for i in range(1,H):
  maze[i,:]=np.minimum(maze[i-1,:]+1,maze[i,:])
for i in range(H-2,-1,-1):
  maze[i,:]=np.minimum(maze[i+1,:]+1,maze[i,:])
for i in range(1,W):
  maze[:,i]=np.minimum(maze[:,i-1]+1,maze[:,i])
for i in range(W-2,-1,-1):
  maze[:,i]=np.minimum(maze[:,i+1]+1,maze[:,i])
  
print(int(np.max(maze)))

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    dist = [[-1] * w for _ in range(h)]
    
    q = deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '
                q.append((i,j))
                dist[i][j] = 0
    
    ans = 0
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if 0 <= y < h and 0 <= x < w and dist[y][x] == -1:
                dist[y][x] = dist[i][j] + 1
                ans = max(ans,dist[y][x])
                q.append((y,x))
    
    print(ans)

if __name__ =='__main__':
    main()

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])

    for i in range(H):
        s = input()
        for j in range(W):
            if s[j]=="
                q.append((i, j))
                m[i][j] = 0
    
    while q:
        y, x = q.popleft()
        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1))
                m[y1][x1] = m[y][x] + 1

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    l = [list(input()) for _ 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 l[i][j]=="
                q.append((i, j))
                m[i][j] = 0
    
    while q:
        y, x = q.popleft()

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1))
                m[y1][x1] = m[y][x] + 1

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Solution (Python):
import collections

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

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

def f(y,x):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = "
            
q = collections.deque()
for i in range(h): 
    for k in range(w):
        if tizu[i][k] == "
            q.append((i,k))
ans = 0
while True:
    l = len(q)
    if l == 0:
        print(ans-1)
        exit()
    for i in range(l):
        yx = q.popleft()
        f(yx[0],yx[1])
    ans += 1

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    H,W = LMIIS()
    A = []
    for _ in range(H):
        A.append(input())
    from copy import deepcopy
    blacks = deque()
    visited = [[False]*W for _ in range(H)]
    for w in range(W):
        for h in range(H):
            if A[h][w] == '
                blacks.append((h,w))
                visited[h][w] = True

    count = -1
    
    while len(blacks) > 0:
        count += 1
        next_blacks = deque()
        while len(blacks) > 0:
            i,j = blacks.pop()
            if 0 <= i-1 and not visited[i-1][j]:
                next_blacks.append((i-1,j))
                visited[i-1][j] = True
            if 0 <= j-1 and not visited[i][j-1]:
                next_blacks.append((i,j-1))
                visited[i][j-1] = True
            if i+1 < H and not visited[i+1][j]:
                next_blacks.append((i+1,j))
                visited[i+1][j] = True
            if j+1 < W and not visited[i][j+1]:
                next_blacks.append((i,j+1))
                visited[i][j+1] = True
        blacks = next_blacks
    print(count)



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h,w = list(map(int,input().split()))
m = [[x for x in input()] for _ in range(h)]
next_que = deque([])
for i in range(h):
  for j in range(w):
    if m[i][j] == '
      next_que.append([i,j])


dh = [1,0,-1,0]
dw = [0,1,0,-1]

def bfs(next_que):
  cnt = -1
  while next_que:
    cnt += 1
    que = list(next_que)
    next_que = deque([])
    for cur in que:
      
      for i in range(4):
        nh = cur[0] + dh[i]
        nw = cur[1] + dw[i]
        
        if nh >= 0 and nh < h and nw >= 0 and nw < w and m[nh][nw] == '.':
          m[nh][nw] = '
          next_que.append([nh,nw])
  
  return cnt



cnt = bfs(next_que) 

print(cnt)

Solution (Python):
import sys
from io import StringIO
import unittest
from collections import deque



def resolve():
    
    h, w = map(int, input().split())

    
    
    
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = deque()

    
    
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "
                que.append((i, j))
                distance[i][j] = 0

    
    while len(que) > 0:

        
        now = que.popleft()

        
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            
            if not distance[target[0]][target[1]] == -1:
                continue

            
            
            que.append(target)
            
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

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

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..
......

......
.
....
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

Solution (Python):
import sys
from io import StringIO
import unittest
from collections import deque



def resolve():
    
    h, w = map(int, input().split())

    
    

    
    
    

        
        
        
        
        


    
    
    
    
    distance = [[-1 for i in range(w)] for j in range(h)]
    
    que = deque()

    
    
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "
                
                que.append((i, j))
                distance[i][j] = 0

    
    while len(que) > 0:

        
        now = que.popleft()

        
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            
            
            
            

            
            if not distance[target[0]][target[1]] == -1:
                continue

            
            
            que.append(target)
            
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

            
            
            

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

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..
......

......
.
....
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque

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


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


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

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W=map(int,input().split())
A=[input() for i in range(H)]
b=[]
l=[[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            l[i][j]=1
            b.append((i,j))
c=0
while 1:
    a=[]
    for i in b:
        if i[0]>0 and not l[i[0]-1][i[1]]:
            a.append((i[0]-1,i[1]))
            l[i[0]-1][i[1]]=1
        if i[1]>0 and not l[i[0]][i[1]-1]:
            a.append((i[0],i[1]-1))
            l[i[0]][i[1]-1]=1
        if i[0]<H-1 and not l[i[0]+1][i[1]]:
            a.append((i[0]+1,i[1]))
            l[i[0]+1][i[1]]=1
        if i[1]<W-1 and not l[i[0]][i[1]+1]:
            a.append((i[0],i[1]+1))
            l[i[0]][i[1]+1]=1
    if not a:
        break
    b=a
    c+=1
print(c)

Solution (Python):
from collections import deque

def bfs(maze, visited, s, h, w):
  queue = deque(s)
  
  va = 0
  while queue:
    y,x = queue.popleft()
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_x < 0 or new_x >= w or new_y < 0 or new_y >=h :
        continue
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        
        visited[new_y][new_x] = visited[y][x] + 1
        va = max(va,visited[new_y][new_x])
        queue.append([new_y, new_x])
  return va


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

maze = [['.' for j in range(w)] for i in range(h)]
visited = [[-1]*(w) for _ in range(h)]
s = []
s_append = s.append
for i in range(h) :
  m1 = input()
  for j in range(w) :
    if m1[j] == '
      s_append([i,j])
      visited[i][j] = 0

print(bfs(maze, visited, s, h, w))

Solution (Python):
from collections import deque

def bfs(maze, visited, s, h, w):
  queue = deque(s)
  
  va = 0
  while queue:
    y,x = queue.popleft()
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_x < 0 or new_x >= w or new_y < 0 or new_y >=h :
        continue
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        
        visited[new_y][new_x] = visited[y][x] + 1
        va = max(va,visited[new_y][new_x])
        queue.append([new_y, new_x])
  return va


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

maze = [['' for j in range(w)] for i in range(h)]
for i in range(h) :
  m1 = input()
  for j in range(w) :
    maze[i][j] = m1[j]

visited = [[-1]*(w) for _ in range(h)]
ans = []
s = []
s_append = s.append
for sy in range(h) :
  for sx in range(w):
    if maze[sy][sx] == '
      s_append([sy,sx])
      maze[sy][sx] = '.'
      visited[sy][sx] = 0

print(bfs(maze, visited, s, h, w))

Solution (Python):
from collections import deque

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

q = deque()

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

while q:
    y,x = q.popleft()
    d = vm[y][x]

    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        yi , xj = y + i , x + j
        if yi >= 0 and xj >= 0 and yi < h and xj < w and vm[yi][xj] == -1 :
            vm[yi][xj] = d +  1
            q.append([yi,xj])
            

print(d)

Solution (Python):
from collections import deque

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

visited = [ [0]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="
            q.append([j,i,0])
            visited[j][i] = 1
        else:
            pass

m = 0
while q:
    y,x,d = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif visited[ny][nx]==0:
            visited[ny][nx] = 1
            q.append([ny,nx,d+1])
            m = max(m,d+1)   
print(m)

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

from collections import deque

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

while len(que)>0:
    n=que.popleft()
    for i in m:
        ni,nj=i[0]+n[0],i[1]+n[1]
        if ni>=0 and nj>=0 and ni<h and nj<w:
            if v[ni][nj]==0:
                v[ni][nj]=1
                que.append([ni,nj,n[2]+1])
print(n[2])

Solution (Python):
import numpy as np

H,W = map(int,input().split())
maze = [list(input())for _ in range(H)]
for i in range(H):
  for j in range(W):
    if maze[i][j]=="
      maze[i][j]=0
    else:
      maze[i][j]=float('INF')
maze=np.array(maze)
for i in range(1,H):
	maze[i,:]=np.minimum(maze[i,:],maze[i-1,:]+1)
for i in range(1,W):
	maze[:,i]=np.minimum(maze[:,i],maze[:,i-1]+1)
for i in range(H-2,-1,-1):
	maze[i,:]=np.minimum(maze[i,:],maze[i+1,:]+1)
for i in range(W-2,-1,-1):
	maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
print(int(np.max(maze)))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

dx = (0,1,0,-1); dy = (1,0,-1,0)
h,w = inpl()
s = []
res = [[0] * w for _ in range(h)]
q = deque()
for i in range(h):
    s.append(list(input()))
    for j in range(w):
        if s[i][j] == '
            q.append((i,j))
mx = 0
while q:
    ny,nx = q.popleft()
    for di in range(4):
        y = ny + dy[di]
        x = nx + dx[di]
        if 0 <= y < h and 0 <= x < w:
            if s[y][x] == '.':
                res[y][x] = res[ny][nx] + 1
                mx = max(mx, res[y][x])
                s[y][x] = '
                q.append((y,x))
print(mx)

Solution (Python):
from collections import deque

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

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

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

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((ny,nx))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())

Solution (Python):
def resolve():

    from collections import deque

    H, W = map(int, input().split())
    maze = [input() for i in range(H)]
    start_list=[]
    for i in range(H):
        for j in range(W):
            if maze[i][j]=='
                start_list.append([i,j])
    INF = 10 ** 20

    visited = [[INF] * W for j in range(H)]


    def bfs(maze):
        queue = deque()
        for [i,j] in start_list:
            queue.append([i,j])
            visited[i][j]=0
        while queue:
            y, x = queue.popleft()
            cnt=0
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and \
                        maze[ny][nx] == "." and visited[ny][nx]==INF:
                        visited[ny][nx] = visited[y][x] + 1
                        queue.append([ny, nx])
        return visited


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

    print(ans)


resolve()

Solution (Python):
import collections

h,w = map(int,input().split())
area = []
q = collections.deque()

for i in range(h):
    area.append(list(input()))
    ls = [(i,j,0) for j in range(w) if area[-1][j] =="
    q.extend(ls)
d = [[-1,0],[0,-1],[1,0],[0,1]]
co = 0
while q:
    y,x,c = q.popleft()
    for dy,dx in d:
        if (0<=y+dy<h) and (0<=x+dx <w):
            if area[y+dy][x+dx] == ".":
                area[y+dy][x+dx] = "
                co = max(c+1,co)
                q.append((y+dy,x+dx,c+1))
print(co)

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


INF=10**9
dp = [[INF] * W for _ in range(H)]


for i in range(H):
    c = INF
    for j in range(W):
        if A[i][j] == '
        elif j>=1: c = dp[i][j-1] + 1
        dp[i][j] = min(dp[i][j], c)


for j in range(W):
    c = INF
    for i in range(H):
        if A[i][j] == '
        elif i>=1: c = dp[i-1][j] + 1
        dp[i][j] = min(dp[i][j], c)


for i in range(H):
    c = INF
    for j in range(W-1,-1,-1):
        if A[i][j] == '
        elif j<W-1: c = dp[i][j+1] + 1
        dp[i][j] = min(dp[i][j], c)


for j in range(W):
    c = INF
    for i in range(H-1,-1,-1):
        if A[i][j] == '
        elif i<H-1: c = dp[i+1][j] + 1
        dp[i][j] = min(dp[i][j], c)

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