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 numpy as np
import copy

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

a = np.array([[0 if (ai[j] == "

for i in range(1, h):
    a[i] = np.minimum(a[i], a[i - 1] + 1)
for i in range(h - 2, -1, -1):
    a[i] = np.minimum(a[i], a[i + 1] + 1)
for i in range(1, w):
    a[:, i] = np.minimum(a[:, i], a[:, i - 1] + 1)
for i in range(w - 2, -1, -1):
    a[:, i] = np.minimum(a[:, i], a[:, i + 1] + 1)

print(int(a.max()))

Solution (Python):
from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                count = max(count,alr[q[0]][q[1]] + 1)
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '

print(count)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
if H==1 and W==1:
    print(0)
    exit()

A=[]
B=deque([])
C=[[-1]*W for i in range(H)]
ans=[]
for h in range(H):
    temp=list(input())
    A.append(temp)
    for w in range(W):
        if A[h][w]=="
            B.append([h,w,0])
            C[h][w]=0
            ans.append(0)



step=[[1,0],[-1,0],[0,1],[0,-1]]

while B:
    P=B.popleft()
    for x,y in step:
        if 0<=P[0]+y<=H-1 and 0<=P[1]+x<=W-1:
            if C[P[0]+y][P[1]+x]==-1:
                B.append([P[0]+y,P[1]+x,P[2]+1])
                C[P[0]+y][P[1]+x]=1
                ans.append(P[2]+1)


print(max(ans))

Solution (Python):
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
que=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            que.append((i, j))
            A[i][j]=1
        else:
            A[i][j]=0
d=[(1,0),(0,1),(-1,0),(0,-1)]
count=0
while que:
    h=[]
    for x,y in que:
        for dx,dy in d:
            nx,ny=x+dx,y+dy
            if 0<=nx<H and 0<=ny<W and A[nx][ny]==0:
                A[nx][ny]=1
                h.append((nx,ny))
    que=h
    count+=1
print(count-1)

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


d = [[-1]*W for _ in range(H)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]


que = deque()
for x in range(W):
    for y in range(H):
        if grid[y][x] == '
            d[y][x] = 0
            que.append([x,y])

while len(que) != 0:
    p = que.popleft()
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        
        if 0 <= nx <= W-1 and 0 <= ny <= H-1 and grid[ny][nx] == '.' and d[ny][nx] == -1:
            que.append([nx,ny])
            d[ny][nx] = d[p[1]][p[0]] + 1



res = 0
for x in range(W):
    for y in range(H):
        res = max(res,d[y][x])
print(res)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
nl = [[] for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            nl[i].append(0)
            q.append([i,j,0])
        else:
            nl[i].append(-1)
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and nl[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        nl[s-1][t] = cnt+1
    if s<h-1 and nl[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        nl[s+1][t] = cnt+1
    if t>0 and nl[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        nl[s][t-1] = cnt+1
    if t<w-1 and nl[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        nl[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(nl[i]))
print(ans)

Solution (Python):
H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="
      a[i,j]=0

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

print(a.max())

Solution (Python):
import numpy as np

h, w = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(h)]) == "
cost = np.full((h, w), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

for i in range(1, h):
    cost[i] = np.minimum(cost[i], cost[i - 1] + 1)

for i in range(h - 1)[::-1]:
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

for i in range(1, w):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i - 1] + 1)

for i in range(w - 1)[::-1]:
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))

Solution (Python):
def grid_bfs(h,w,start,maxD):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = deque()
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h):
                if (distance[ny][nx] > distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
                    if maxD<distance[ny][nx]:
                        maxD = distance[ny][nx]
    return maxD
def examA():
    H, W = LI()
    A = [[1 if a == "
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]==1:
                start.append([i,j])
    ans = grid_bfs(H,W,start,0)

    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Solution (Python):
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    grid = ['W'] * (W + 2)
    for i in range(H):
        grid += ['W'] + list(f_i.readline().rstrip()) + ['W']
    grid += ['W'] * (W + 2)
    
    q = deque()
    for i, cell in enumerate(grid):
        if cell == '
            q.append((i, 0)) 
    move = (1, -1, W + 2, -W - 2)
    
    while q:
        pos, count = q.popleft()
        for mv in move:
            next_pos = pos + mv
            if grid[next_pos] == '.':
                grid[next_pos] = '
                q.append((next_pos, count + 1))
    
    print(count)
    
solve()

Solution (Python):

from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="
            a[j+1]=True
            d.append((i+1,j+1))
    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = []
    ql = collections.deque()
    for i in range(h):
        al = list(str(readline().rstrip().decode('utf-8')))
        ta = []
        for j in range(w):
            if al[j] == ".":
                ta.append(True)
            else:
                ta.append(False)
                ql.append([0, i, j])
        a.append(ta)

    mc = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mc = max(mc, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv]:
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = False
        else:
            break
    print(mc)


if __name__ == '__main__':
    solve()

Solution (Python):
h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [[1 if a == "
L = []
for i in range(H):
    for j in range(W):
        if A[i][j]: L.append((i, j))
def BFS():
    Q = deque(L)
    D = [[-1] * W for _ in range(H)]
    for i, j in L:
        D[i][j] = 0
    while Q:
        i, j = Q.popleft()
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ni, nj = i+di, j+dj
            if 0 <= ni < H and 0 <= nj < W:
                if D[ni][nj] == -1:
                    D[ni][nj] = D[i][j] + 1
                    Q.append((ni, nj))
    return D

print(max([max(a) for a in BFS()]))

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

row, column = map(int, input().split())
map_ = [[c == "

queue = deque([(i, j) for j in range(column) for i in range(row) if map_[i][j]])

def bfs(maze, queue):
    depth = 0
    while True:
        depth += 1
        nextqueue = deque()
        while queue:
            posr, posc = queue.popleft()
            for dr, dc in zip([1, -1, 0, 0], [0, 0, 1, -1]):
                nextr = posr + dr
                nextc = posc + dc
                if 0 <= nextr < row and 0 <= nextc < column and not maze[nextr][nextc]:
                    maze[nextr][nextc] = True
                    nextqueue.append((nextr, nextc))
        if nextqueue:
            queue = copy(nextqueue)
        else:
            return depth - 1

print(bfs(map_, queue))

Solution (Python):
from fractions import gcd

from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    a = [list(input()) for i in range(h)]
    queue = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "
                queue.append((i, j))

    visited = [[-1 for i in range(w)] for j in range(h)]
    ans = 0
    nqueue = deque()
    while queue:
        x, y = queue.popleft()
        visited[x][y] = 1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = x + i
            ny = y + j
            if nx >= 0 and ny >= 0 and nx < h and ny < w:
                if visited[nx][ny] == -1 and a[nx][ny] != "
                    nqueue.append([nx, ny])
                    visited[nx][ny] = 1
                    a[nx][ny] = "
        
        if len(queue) == 0:
            queue = nqueue
            nqueue = deque()
            ans += 1
        
    print(ans-1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
p=[list("
q=deque([])
for i in range(1,h+1):
	for j in range(1,w+1):
		if p[i][j]=='
			p[i][j]=0
			q.append([i,j])
d=[(1,0),(-1,0),(0,1),(0,-1)]
while q:
	x,y=q.popleft()
	for dx,dy in d:
		if p[x+dx][y+dy]==".":
			p[x+dx][y+dy]=p[x][y]+1
			q.append([x+dx,y+dy])
ans=0
for i in range(1,h+1):
	for j in range(1,w+1):
		ans=max(ans,p[i][j])
print(ans)

Solution (Python):
from collections import deque


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

INF = 10 ** 5
d = [[10 ** 5] * 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))

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

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] != '

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

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

print(ans)

Solution (Python):
h, w = map(int, input().split())
grid = [[0]*(w) for _ in range(h)]

black = []
for i in range(h):
    for j, k in enumerate(input()):
        if k == "
            black.append((i, j))
            grid[i][j] = 1

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while True:
    paint = []
    while black:
        x, y = black.pop()
        for nx, ny in d:
            if x+nx == -1 or x+nx == h or y+ny == -1 or y+ny == w:
                continue
            if not grid[nx + x][ny + y]:
                grid[nx + x][ny + y] = 1
                paint.append((nx + x, ny + y))

    if len(paint) == 0:
        break
    black = paint[:]
    ans += 1

print(ans)

Solution (Python):
h, w = map(int, input().split())
grid = [[0]*(w+2) for _ in range(h+2)]

black = []
for i in range(h):
    for j, k in enumerate(input()):
        if k == "
            black.append((i + 1, j + 1))
            grid[i+1][j+1] = 1

ans = 0
d = ((0, 1),
     (1, 0),
     (0, -1),
     (-1, 0),)
while True:
    paint = []
    while black:
        x, y = black.pop()
        if x == 0 or x == h + 1 or y == 0 or y == w + 1:
            continue
        else:
            for nx, ny in d:
                if not grid[nx + x][ny + y]:
                    if x+nx == 0 or x+nx == h + 1 or y+ny == 0 or y+ny == w + 1:
                        continue
                    grid[nx + x][ny + y] = 1
                    paint.append((nx + x, ny + y))

    if len(paint) == 0:
        break
    black = paint[:]
    ans += 1

print(ans)

Solution (Python):
import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[-1]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            dp[i][j] = 0
            q.append([i, j])


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] == -1:
            dp[x-1][y] = dp[x][y]+1
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] == -1:
            dp[x+1][y] = dp[x][y]+1
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] == -1:
            dp[x][y-1] = dp[x][y]+1
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] == -1:
            dp[x][y+1] = dp[x][y]+1
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)

Solution (Python):
import collections
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
dp = [[H+W]*W for i in range(H)]

q = collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            dp[i][j] = 0
            q.append([i, j])
            break
    if q:
        break


while(q):
    x, y = q.popleft()
    if x > 0:
        if dp[x-1][y] > dp[x][y]+1:
            if A[x-1][y] == ".":
                dp[x-1][y] = dp[x][y]+1
            else:
                dp[x-1][y] = 0
            q.append([x-1, y])
    if x < H-1:
        if dp[x+1][y] > dp[x][y]+1:
            if A[x+1][y] == ".":
                dp[x+1][y] = dp[x][y]+1
            else:
                dp[x+1][y] = 0
            q.append([x+1, y])
    if y > 0:
        if dp[x][y-1] > dp[x][y]+1:
            if A[x][y-1] == ".":
                dp[x][y-1] = dp[x][y]+1
            else:
                dp[x][y-1] = 0
            q.append([x, y-1])
    if y < W-1:
        if dp[x][y+1] > dp[x][y]+1:
            if A[x][y+1] == ".":
                dp[x][y+1] = dp[x][y]+1
            else:
                dp[x][y+1] = 0
            q.append([x, y+1])
ans = 0
for i in range(H):
    ans = max(ans, max(dp[i]))
print(ans)

Solution (Python):
from collections import deque


h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
d=[[-1]*w for i in range(h)]
que=deque([])
dd=((1,0),(0,1),(-1,0),(0,-1))
for i in range(h):
    for j in range(w):
        if maze[i][j]=="
            que.append((i,j))           
            d[i][j]=0
ans=0
while que:
    p=que.popleft()
    ans=d[p[0]][p[1]]
    for dx,dy in dd:
        nx=p[0]+dx
        ny=p[1]+dy
        if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="
            d[nx][ny]=ans+1
            que.append((nx,ny))  
print(ans)

Solution (Python):
from collections import deque

def main():
    h,w=map(int,input().split())
    maze=[list(input()) for i in range(h)]
    d=[[-1]*w for i in range(h)]
    que=deque([])
    dd=((1,0),(0,1),(-1,0),(0,-1))
    for i in range(h):
        for j in range(w):
            if maze[i][j]=="
                que.append((i,j))           
                d[i][j]=0
    ans=0
    while que:
        p=que.popleft()
        ans=d[p[0]][p[1]]
        for dx,dy in dd:
            nx=p[0]+dx
            ny=p[1]+dy
            if 0<=nx and nx<h and 0<=ny and ny<w and maze[nx][ny]!="
                d[nx][ny]=ans+1
                que.append((nx,ny))  
    return ans
if __name__=='__main__':
    print(main())

Solution (Python):
from collections import deque

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

INF = 10**7


vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)


q = deque()
for i, vi in enumerate(p):
    for j, vj in enumerate(vi):
        if vj == '
            q.appendleft((j, i))
            
qans = deque()


def bfs(q):
    for i in range(INF):
        
        if len(q) == 0:
            return qans

        
        x, y = map(int, q.pop())

        
        for j in range(4):
            nx, ny = x+vx[j], y+vy[j]

            
            if nx < 0 or w <= nx or ny < 0 or h <= ny or p[ny][nx] == '
                continue

            p[ny][nx] = '
            qans.appendleft((nx, ny))


for i in range(INF):
    qans = deque()
    q = bfs(q)
    
    if len(q) == 0:
        ans = i
        break
    
print(ans)

Solution (Python):
from collections import deque

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


INF = 10**7



vx = (0, -1, 0, 1)
vy = (-1, 0, 1, 0)



q = deque()
bcnt = 0
for i, vi in enumerate(p):
    for j, vj in enumerate(vi):
        if vj == '
            q.appendleft((j, i))
            bcnt+=1
            
qans = deque()
            
def bfs(q):
    for i in range(INF):
        
        if len(q) == 0:
            return qans

        
        x, y = map(int, q.pop())


        
        for j in range(4):
            nx, ny = x+vx[j], y+vy[j]

            
            if nx < 0 or w <= nx or ny < 0 or h <= ny or p[ny][nx] == '
                continue

            p[ny][nx] = '
            qans.appendleft((nx, ny))

def printmap(a):
    for i in a:
        print(i)
        


for i in range(INF):
    qans = deque()
    q = bfs(q)


    
    if len(q) == 0:
        ans = i
        break
    
print(ans)

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


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if grid[nx][ny] == '.':
                res_q.append((nx, ny))
                grid[nx][ny] = '
    return res_q


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

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) + [False] for _ in range(H)]
grid = grid + [[False for _ in range(W + 1)]]
d = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in d:
            nx = x + dx
            ny = y + dy

            if grid[nx][ny] == '.':
                res_q.append((nx, ny))
                grid[nx][ny] = '
    return res_q


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

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)

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




def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '
                res_q.append((nx, ny))
                grid[nx][ny] = '
    return res_q


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

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)

Solution (Python):
from collections import deque
import copy

h,w = map(int, input().split())
s = [["
q = deque([(i, j) for i in range(1,h+1) for j in range(1,w+1) if s[i][j] == "
white = 0
while True:
  q2 = deque()
  while q:
    a,b = q.popleft()
    if s[a-1][b] == ".":
      s[a-1][b] = "
      q2.append((a-1,b))
    if s[a+1][b] == ".":
      s[a+1][b] = "
      q2.append((a+1,b))
    if s[a][b-1] == ".":
      s[a][b-1] = "
      q2.append((a,b-1))
    if s[a][b+1] == ".":
      s[a][b+1] = "
      q2.append((a,b+1))   
  if q2:
    q = copy.copy(q2)
    white += 1
  else:
    print(white)
    break

Solution (Python):
from collections import deque
H, W = map(int, input().split())

gridgraph = [list(input()) for _ in range(H)]
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0
            
while len(q):
    cy, cx = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)

Solution (Python):
import sys
from collections import deque
H, W = map(int, input().split())
gridgraph = []
for line in sys.stdin.readlines():
    line = line.rstrip()
    gridgraph.append(list(line))
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0

while len(q):
    cy, cx = q.popleft()

    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)

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

m=[[-1 for i in range(W+2)]]
mm=[[-1]+[0 for i in range(W)]+[-1] for j in range(H)]
m=m+mm+m

nexts=[]
for i in range(1, H+1):
  c=input()
  for j in range(1, W+1):
    if c[j-1]=='
      nexts.append([i, j])
      m[i][j]=1
      
def f(math, in_nexts):
  n=len(in_nexts)
  out_nexts=[]
  for i in range(n):
    x=in_nexts[i][0]
    y=in_nexts[i][1]
    if math[x-1][y]==0:
      math[x-1][y]=math[x][y]+1
      out_nexts.append([x-1, y])
    if math[x+1][y]==0:
      math[x+1][y]=math[x][y]+1
      out_nexts.append([x+1, y])
    if math[x][y-1]==0:
      math[x][y-1]=math[x][y]+1
      out_nexts.append([x, y-1])
    if math[x][y+1]==0:
      math[x][y+1]=math[x][y]+1
      out_nexts.append([x, y+1])
      
  return math, out_nexts

counter=0
while len(nexts)>0:
  m, nexts=f(m, nexts)
  counter+=1
  
print(counter-1)

Solution (Python):
def main():

    H, W = map(int, input().split())
    A = []
    white = 0
    h = []
    for i in range(H):
        A.append(list(input()))
        for j in range(W):
            if A[i][j] == '
                h.append([i, j])
            else:
                white += 1

    cnt = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while h and white > 0:
        temp = []
        cnt += 1
        for i, j in h:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0<=i1<H and 0<=j1<W and A[i1][j1] == '.':
                    temp.append([i1, j1])
                    A[i1][j1] = '
                    white -= 1
        h = temp
    return cnt

if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
from collections import deque
if sys.platform =='win32':
  sys.stdin=open('./input.txt')
input = sys.stdin.readline
def MAP(): return [int(x) for x in input().split()]

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

H, W = [int(s) for s in input().split()]

M = []

for i in range(H):
	M.append([s for s in input().rstrip()]) 

syx = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '


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

for s in syx:
	dist[s[0]][s[1]] = 0

queue.append(syx)

while queue:
	nodelist = queue.popleft()
	
	nextnode = []

	for node in nodelist:
		y, x = node
		
		
		for i in range(4):
			ny = y+dy[i]
			nx = x+dx[i]
			
			
			if ny>=H or ny<0 or nx>=W or nx<0:
				continue
			if dist[ny][nx] != -1:
				continue
			
			if M[ny][nx] == '.':
				dist[ny][nx] = dist[y][x]+1
				nextnode.append([ny,nx])

	
	if len(nextnode)!=0:
		queue.append(nextnode)

ans = 0
for d in dist:
  ans = max(ans, max(d))
print(ans)

Solution (Python):





from collections import deque

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


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


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



for i in range(H):
    for k in range(W):
        if field[i][k] == "
            dist[i][k] = 0
            que_x.append(i)
            que_y.append(k)







while que_x and que_y:
    x = que_x[0]
    y = que_y[0]
    que_x.popleft()
    que_y.popleft()
    for direct in range(4):
        nx = x + dx[direct]
        ny = y + dy[direct]
        if nx < 0 or H <= nx or ny < 0 or W <= ny:      
            continue
        if dist[nx][ny] == -1:      
            que_x.append(nx)
            que_y.append(ny)
            dist[nx][ny] = dist[x][y] + 1       


tmp = [0] * H
for i in range(H):
    tmp[i] = max(dist[i])

print(max(tmp))

Solution (Python):
h,w=map(int,input().split())
field=[]
new=False
black=[]
for i in range(h):
	b=[]
	a=input()
	for j in range(w):
		if a[j]=="
			b.append(1)
			black.append([i,j])
		else:
			b.append(0)
	field.append(b)
ans=0
while len(black):
	black_new=[]
	q=len(black)
	for k in range(q):
		i,j=black[k][0],black[k][1]
		if i!=0 and field[i-1][j]==False:
			field[i-1][j]=True
			black_new.append([i-1,j])
		if i!=h-1 and field[i+1][j]==False:
			field[i+1][j]=True
			black_new.append([i+1,j])
		if j!=0 and field[i][j-1]==False:
			field[i][j-1]=True
			black_new.append([i,j-1])
		if j!=w-1 and field[i][j+1]==False:
			field[i][j+1]=True
			black_new.append([i,j+1])
	black=black_new
	ans+=1
print(ans-1)

Solution (Python):
from collections import deque

H,W=map(int,input().split())
d=[]
for i in range(H):    
    d.append([0 if c=='

q=deque()
for i in range(H):
    for j in range(W):
        if not d[i][j]:
            q.append((i,j))

while q:
    u=q.popleft()
    ui,uj=u
    for v in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        vi,vj=v
        if 0<=vi<=H-1 and 0<=vj<=W-1 and d[vi][vj]==-1:
            d[vi][vj]=d[ui][uj]+1
            q.append(v)

print(max(max(di) for di in d))

Solution (Python):
from collections import deque

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

q = []
for y in range(H) :
    for x in range(W) :
        if A[y][x] == '
            q.append((y, x))

ret = 0
while True :
    r = []
    while q :
        cy, cx = q.pop()
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.' :
                A[ny][nx] = '
                r.append((ny, nx))
    ret += 1
    if len(r) == 0 :
        break
    
    q = r
    
print(ret - 1)