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 defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['
    H = len(c)
    W = len(c[0])
    distance_limit = H*W+1
    dist = [[distance_limit]*W for i in range(H)]

    q = deque()

    q_append = q.append
    q_popleft = q.popleft

    if (type(sy)==list) or (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q_append((sy, sx))

    while q:
        y, x = q_popleft()
        d = dist[y][x]
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx) and (not return_maximum_distance):
                        return (d+1)
                    elif (dist[y+dy][x+dx] > d+1):
                        dist[y+dy][x+dx] = d+1
                        q_append((y+dy, x+dx))
    if (return_maximum_distance):
        return d
    return -1

H, W = LI()
c = SR(H)

sy = []
sx = []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="
            sy.append(i)
            sx.append(j)

print(bfs(c, sy, sx, return_maximum_distance=True))



def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['
            H = len(c)
            W = len(c[0])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['
    H = len(c)
    W = len(c[0])
    distance_limit = H*W+1
    dist = [[distance_limit]*W for i in range(H)]

    q = deque()

    q_append = q.append
    q_popleft = q.popleft

    if (type(sy)==list) or (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q_append((sy, sx))

    while q:
        y, x = q_popleft()
        d = dist[y][x]
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx) and (not return_maximum_distance):
                        return (d+1)
                    elif (dist[y+dy][x+dx] > d+1):
                        dist[y+dy][x+dx] = d+1
                        q_append((y+dy, x+dx))
    if (return_maximum_distance):
        return d
    return -1

H, W = LI()
c = SR(H)

sy = []
sx = []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="
            sy.append(i)
            sx.append(j)

print(bfs(c, sy, sx, return_maximum_distance=True))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['
    H = len(c)
    W = len(c[0])
    distance_limit = H*W+1
    dist = [[distance_limit]*W for i in range(H)]

    q = deque()

    q_append = q.append
    q_popleft = q.popleft

    if (type(sy)==list) or (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q_append((sy, sx))

    while q:
        y, x = q_popleft()
        d = dist[y][x]
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (dist[y+dy][x+dx] > d+1):
                        dist[y+dy][x+dx] = d+1
                        q_append((y+dy, x+dx))
                    if (y+dy==gy) and (x+dx==gx):
                        return (d+1)
    if (return_maximum_distance):
        return d
    return -1

H, W = LI()
c = SR(H)

sy = []
sx = []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="
            sy.append(i)
            sx.append(j)

print(bfs(c, sy, sx, sy, sx, return_maximum_distance=True))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(sy=0, sx=0, c=[['.']], gy=0, gx=0, blocks=['
    H = len(c)
    W = len(c[0])
    dire = [(1,0), (0,1), (-1,0), (0,-1)]
    dist = [[1000000007]*W for i in range(H)]

    q = deque()

    if (type(sy)==list) and (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q.append((sy, sx))

    if (return_maximum_distance):
        while q:
            y, x = q.popleft()
            for dy, dx in dire:
                if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                    if (c[y+dy][x+dx] in blocks):
                        continue
                    elif (dist[y+dy][x+dx] > dist[y][x]+1):
                            dist[y+dy][x+dx] = dist[y][x]+1
                            q.append((y+dy, x+dx))
        maximum_distance = 0
        for i in range(H):
            for j in range(W):
                if (dist[i][j] < 1000000007):
                    maximum_distance = max(dist[i][j], maximum_distance)
        return maximum_distance

    else:
        while q:
            y, x = q.popleft()
            for dy, dx in dire:
                if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                    if (c[y+dy][x+dx] in blocks):
                        continue
                    else:
                        if (y+dy==gy) and (x+dx==gx):
                            return (dist[y][x]+1)
                        elif (dist[y+dy][x+dx] > dist[y][x]+1):
                            dist[y+dy][x+dx] = dist[y][x]+1
                            q.append((y+dy, x+dx))
        return -1

H, W = LI()
c = SR(H)

sy, sx = [], []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="
            sy.append(i)
            sx.append(j)

print(bfs(sy, sx, c, return_maximum_distance=True))

Solution (Python):
import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)

Solution (Python):
import collections
h,w = map(int,input().split())
q = collections.deque()
A = []
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        if s[j] == '.':
            L.append(s[j])
        else:
            L.append(0)
            q.append([i,j])
    A.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    cur = q.popleft()
    for i in range(4):
        y = cur[0]+dy_dx[i][0]
        x = cur[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if A[y][x] == '.':
                A[y][x] = A[cur[0]][cur[1]]+1
                q.append([y,x])
ans = 0
for i in range(h):
    for j in range(w):
        if ans < A[i][j]:
            ans = A[i][j]
print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)


def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))

Solution (Python):
from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("
        b = [(h, w) for w, e in enumerate(a) if e == "
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

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

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))

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

black, white = [], 0
for y, line in enumerate(STAGE):
	for x, cell in enumerate(line):
		if "
			black += [(y, x)]
		else:
			white += 1

stage = STAGE
ds = ((0, 1), (1, 0), (0, -1), (-1, 0))

def get_next(p, d):
	n = (p[0] + d[0], p[1] + d[1])
	if 0 <= n[0] < H and 0 <= n[1] < W:
		return n
	return None

def set_val(p, v):
	global stage
	stage[p[0]][p[1]] = v

def get_val(p):
	return stage[p[0]][p[1]]

count = 0
while white:
	count += 1
	next_black = []
	for b in black:
		for d in ds:
			n = get_next(b, d)
			if n:
				v = get_val(n)
				if "." == v:
					white -= 1
					set_val(n, "
					next_black += [n]
	black = next_black

print(count)

Solution (Python):



from collections import deque

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

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)

Solution (Python):
import numpy as np
import sys


buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())
black = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'

INF = 10 ** 9
dist = np.zeros((H,W),dtype=np.int32)
dist[~black[:,:-1]] = INF

for n in range(1,H):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,W):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)

Solution (Python):
import numpy as np
import sys


buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())
black = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'

INF = 10 ** 9
dist = np.zeros((H,W),dtype=np.int32)
dist[~black[:,:-1]] = INF

for n in range(1,H):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,W):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)

Solution (Python):
import numpy as np
import sys



buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
black = np.zeros((R+2,C+2),dtype=np.bool)
black[1:-1,1:] = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'

INF = 10 ** 9
dist = np.zeros((R,C),dtype=np.int32)
dist[~black[1:-1,1:-1]] = INF

for n in range(1,R):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(R-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,C):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(C-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)

Solution (Python):
import numpy as np

h, w = map(int, input().split())
max_value = h + w
values = []

for i in range(h):
  values.append([0 if i == '
values = np.array(values)

for x in range(w - 1):
  values[:, x+1] = np.minimum(values[:, x] + 1, values[:, x+1])
for x in range(w - 1, 0 , -1):
  values[:, x-1] = np.minimum(values[:, x-1], values[:, x] + 1)
for x in range(h - 1):
  values[x+1, :] = np.minimum(values[x, :] + 1,values[x+1, :])
for x in range(h - 1, 0, -1):
  values[x-1, :] = np.minimum(values[x, :] + 1, values[x-1, :])

print(np.max(values))

Solution (Python):
import numpy as np
h,w=map(int,input().split())
graph=[[0 if i=='
graph=np.array(graph)
for x in range(w-1):
    graph[:,x+1]=np.minimum(graph[:,x]+1,graph[:,x+1])
for x in range(w-1,0,-1):
    graph[:,x-1]=np.minimum(graph[:,x]+1,graph[:,x-1])
for y in range(h-1):
    graph[y+1,:]=np.minimum(graph[y,:]+1,graph[y+1,:])
for y in range(h-1,0,-1):
    graph[y-1,:]=np.minimum(graph[y,:]+1,graph[y-1,:])

print(int(np.max(graph)))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def solve():
	H, W = MAP()
	A = [input() for _ in range(H)]

	count = [[0]*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))
	

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

	while len(q) >= 1:
		i, j = q.popleft()
		
		for x, y in zip(dx, dy):
			ny = i + y
			nx = j + x
			if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "
				count[ny][nx] = count[i][j] + 1
				q.append((ny, nx))

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

if __name__ == "__main__":
	solve()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
A = [input() for _ in range(H)]

count = [[0]*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))


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

while len(q) >= 1:
	i, j = q.popleft()
	
	for x, y in zip(dx, dy):
		ny = i + y
		nx = j + x
		if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "
			count[ny][nx] = count[i][j] + 1
			q.append((ny, nx))

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

print(ans)

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

maps = [[-1]*W for _ in range(H)]
mv=[[1,0],[-1,0],[0,1],[0,-1]]
cnt = 0
li=[]
que = []
for h,i in enumerate(A):
    for w,j in enumerate(i):
        if(j=='
            maps[h][w]=0
            que.append([h,w])
while(True):
    next_que=[]
    while(que):
        x = que.pop()
        now = maps[x[0]][x[1]]
        for i in mv:
            if(0<=x[0]+i[0]<H and 0<=x[1]+i[1]<W):
                if(maps[x[0]+i[0]][x[1]+i[1]]==-1):
                    maps[x[0]+i[0]][x[1]+i[1]]=now+1
                    next_que.append([x[0]+i[0],x[1]+i[1]])
    if(len(next_que)==0):
        break
    else:
        cnt += 1
        que=next_que
print(cnt)

Solution (Python):
import numpy as np


def solve():
    h, w = map(int, input().split(' '))
    max_value = h + w
    values = []
    for i in range(h):
        values.append([0 if i == '
    values = np.array(values)

    for x in range(w - 1):
        values[:, x+1] = np.minimum(values[:, x] + 1, values[:, x+1])
    for x in range(w - 1, 0 , -1):
        values[:, x-1] = np.minimum(values[:, x-1], values[:, x] + 1)
    for x in range(h - 1):
        values[x+1, :] = np.minimum(values[x, :] + 1,values[x+1, :])
    for x in range(h - 1, 0, -1):
        values[x-1, :] = np.minimum(values[x, :] + 1, values[x-1, :])
    print(np.max(values))


solve()

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

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

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

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

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

Solution (Python):
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    q = deque()
    visited = [[False] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "
                q.append((i, j, 0))
                visited[i][j] = True
    ans = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        ans = max(ans, cost)
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                q.append((ni, nj, cost+1))
                visited[ni][nj] = True
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
graph = [[float('inf')] * W for _ in range(H)]
deq = deque()

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

while deq:
    x, y = deq.popleft()
        
    for i, j in offsets:
        if (not 0 <= x + i < H) or (not 0 <= y + j < W):
            continue

        if graph[x + i][y + j] < float('inf'):
            continue

        if grid[x + i][y + j] == '
            continue
            
        graph[x + i][y + j] = graph[x][y] + 1
        deq.append((x + i, y + j))
        
print(max(max(v) for v in graph))

Solution (Python):
def main():
  h,w = map(int,input().split())

  q = []
  reached = [[True]*(w+2)]
  for i in range(1, h+1):
    reached.append([True] + [s == '
    for j in range(1,w+1):
      if reached[i][j]: q.append((i,j))
  reached.append([True]*(w+2))

  res = 0
  for i in range(100000000):
    qq = []
    for k,l in q:
      if not reached[k+1][l]:
        qq.append((k+1, l))
        reached[k+1][l] = True
      if not reached[k][l+1]:
        qq.append((k, l+1))
        reached[k][l+1] = True
      if not reached[k-1][l]:
        qq.append((k-1, l))
        reached[k-1][l] = True
      if not reached[k][l-1]:
        qq.append((k, l-1))
        reached[k][l-1] = True
    if len(qq) == 0:
      break
    else:
      pass

    q = qq
    res += 1

  print(res)
  return 0

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
h, w=map(int, input().split())
a=[]
need_visited=[[0 for i in range(w)] for j in range(h)]
stack=deque()
for i in range(h):
    a.append(list(input()))

for i in range(h):
    for j in range(w):
        if a[i][j]=="
            stack.append([i, j])



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


while len(stack)!=0:
    now_point=stack.popleft()
    for i in range(4):
        target_h=now_point[0]+dx[i]
        target_w=now_point[1]+dy[i]
        if 0<=target_h<h and 0<=target_w<w:
            if a[target_h][target_w]==".":
                need_visited[target_h][target_w]=need_visited[now_point[0]][now_point[1]]+1
                a[target_h][target_w]="
                stack.append([target_h, target_w])
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, need_visited[i][j])
print(ans)

Solution (Python):
from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

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

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

Solution (Python):
from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

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

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

Solution (Python):
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = []
for h in range(H):
    for w in range(W):
        if cell[h][w] == '
            painted.append([h, w])

ans = 0
while len(painted) > 0:
    to_be_painted = []
    for blackcell in painted:
        h = blackcell[0]
        w = blackcell[1]
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
                cell[nh][nw] = '
                to_be_painted.append([nh, nw])
    painted = to_be_painted
    if len(painted) > 0: ans += 1

print(ans)

Solution (Python):
from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

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

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

Solution (Python):
"""
解説と提出 
"""

from collections import deque


def solve():
    H, W = map(int, input().split())
    
    
    
    queue1 = []
    queue2 = []
    mass = []
    mass.append([False] * (W + 2))  
    for Hi in range(1, H + 1):
        mass.append([False] + [s == '.' for s in list(input())] + [False])
        for Wi in range(1, W + 1):
            if not mass[Hi][Wi]:
                queue1.append((Hi, Wi))
    mass.append([False] * (W + 2))  
    import datetime
    d = datetime.datetime.now()
    count = -1
    while True:
        
        if len(queue1) == 0:
            break
        for h, w in queue1:
            
            if mass[h][w - 1]:
                mass[h][w - 1] = False
                queue2.append((h, w - 1))
            
            if mass[h][w + 1]:
                mass[h][w + 1] = False
                queue2.append((h, w + 1))
            
            if mass[h + 1][w]:
                mass[h + 1][w] = False
                queue2.append((h + 1, w))
            
            if mass[h - 1][w]:
                mass[h - 1][w] = False
                queue2.append((h - 1, w))

        count += 1
        queue1 = queue2
        queue2 = []
    print(count)

    


if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W = map(int,input().split())
A = list(list(input()) for _ in range(H))
dirc = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] =="
            A[i][j] = 0
            q.append((i,j))
ans = 0
while q:
    y,x = q.popleft()
    for dy,dx in dirc:
        if 0<=dy+y<H and 0<=dx+x<W and A[dy+y][dx+x]==".":
            A[dy+y][dx+x] = A[y][x]+1
            ans = max(ans,A[dy+y][dx+x])
            q.append((dy+y,dx+x))

print(ans)

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


que = []
for k in range(1,H+1):
    for l in range(1,W+1):
        if A[k][l] == "
            que.append([k,l])
if len(que) == H*W:
    print(0)
    exit(0)
ans = 0
while True:
    t = []
    while len(que) > 0:
        s = que.pop()
        k, l = s[0], s[1]
        if A[k][l-1] == ".":
            A[k][l-1] = "
            t.append([k,l-1])
        if A[k][l+1] == ".":
            A[k][l+1] = "
            t.append([k,l+1])
        if A[k-1][l] == ".":
            A[k-1][l] = "
            t.append([k-1,l])
        if  A[k+1][l] == ".":
            A[k+1][l] = "
            t.append([k+1,l])
    if len(t) > 0:
        ans += 1
        que = t
    else:
        break
print(ans)