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

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

Map = [[] for _ in range(H)]
reached = [[False] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "
            cnt += 1
            reached[y][i] = True
            if i + 1 < W and not reached[y][i + 1]:
                reached[y][i + 1] = True
                tempList.append((i + 1, y))

            if i > 0 and not reached[y][i - 1]:
                reached[y][i - 1] = True
                tempList.append((i - 1, y))

            if y + 1 < H and not reached[y + 1][i]:
                reached[y + 1][i] = True
                tempList.append((i, y + 1))

            if y > 0 and not reached[y - 1][i]:
                reached[y - 1][i] = True
                tempList.append((i, y - 1))
if cnt==H*W:
    print(0)
    exit()

q.append(tempList)


def BFS(blist):
    global count
    tList = []

    count += 1

    for (x, y) in blist:
        if x+1<W and not reached[y][x + 1]:
            reached[y][x + 1] = True
            tList.append((x + 1, y))

        if x-1>=0 and not reached[y][x - 1]:
            reached[y][x - 1] = True
            tList.append((x - 1, y))

        if y+1<H and not reached[y + 1][x]:
            reached[y + 1][x] = True
            tList.append((x, y + 1))

        if y-1>=0 and not reached[y - 1][x]:
            reached[y - 1][x] = True
            tList.append((x, y - 1))

    if tList:
        q.append(tList)


while q:
    BFS(q.popleft())

print(count)

Solution (Python):
def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


H, W = map(int, input().split())
m = [[0 if c == '
queue = deque()
for i, r in enumerate(m):
    for j, n in enumerate(r):
        if n == 0:
            queue.append((i, j))
while queue:
    p, q = queue.popleft()
    if 0 < p and m[p - 1][q] > m[p][q] + 1:
        m[p - 1][q] = m[p][q] + 1
        queue.append((p - 1, q))
    if 0 < q and m[p][q - 1] > m[p][q] + 1:
        m[p][q - 1] = m[p][q] + 1
        queue.append((p, q - 1))
    if p < H - 1 and m[p + 1][q] > m[p][q] + 1:
        m[p + 1][q] = m[p][q] + 1
        queue.append((p + 1, q))
    if q < W - 1 and m[p][q + 1] > m[p][q] + 1:
        m[p][q + 1] = m[p][q] + 1
        queue.append((p, q + 1))
_max = 0
for r in m:
    _max = max(_max, max(r))
print(_max)

Solution (Python):
from collections import deque

def bfs(grid, costs, queue, wall, res):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while res:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
            res -= 1
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0] * (W+2)]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0] * (W+2))
grid.append(edges)
print(bfs(grid, costs, queue, wall, H*W - len(queue)))

Solution (Python):
from collections import deque

def bfs(grid, costs, queue, wall, res):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while res:
        y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([y_,x_])
            grid[y_][x_] = wall
            costs[y_][x_] = costs[y][x] + 1
            ans = max(ans, costs[y_][x_])
            res -= 1
    return ans

import sys
input = sys.stdin.readline
H,W = map(int, input().split())
wall = '
queue = deque([])
edges = [wall for _ in range(W+2)]
grid = [edges]
costs = [[0 for _ in range(W+2)]]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([i,j])
    grid.append(S)
    costs.append([0 for _ in range(W+2)])
grid.append(edges)
print(bfs(grid, costs, queue, wall, H*W - len(queue)))

Solution (Python):
from collections import deque

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

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

ans = 0
while q:
    nq = deque()
    while q:
        h, w = q.popleft()
        if h > 0 and A[h - 1][w] == '.':
            A[h - 1][w] = '
            nq.append((h - 1, w))
        if h < H - 1 and A[h + 1][w] == '.':
            A[h + 1][w] = '
            nq.append((h + 1, w))
        if w > 0 and A[h][w - 1] == '.':
            A[h][w - 1] = '
            nq.append((h, w - 1))
        if w < W - 1 and A[h][w + 1] == '.':
            A[h][w + 1] = '
            nq.append((h, w + 1))
    if not nq:
        break
    q = nq
    ans += 1
print(ans)

Solution (Python):
import sys
import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    H, W = MAP()
    A = [INPUT() for _ in range(H)]
    A = np.array([[(Ai[j] != "
    print(distance_transform_cdt(A, metric="taxicab").max())


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "


    
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "


    
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "


    
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == "__main__":
    main()

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

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

que = deque()

white = h * w


for i in range(h):
    for j in range(w):
        if a[i][j] == "
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "
                white -= 1
                que.append([ny, nx])


print(count)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
   

H, W = LI()
A = []
for _ in range(H):
    A.append(S())
seen = [[0 for _ in range(W)] for __ in range(H)]

def main():
    q = deque()
    ans = 0
    for i, cc in enumerate(A):
        for j, c in enumerate(cc):
            if c == '
                q.append((i, j, 0))
                seen[i][j] = 1
    while q:
        cur_row, cur_col, num = q.popleft()
        for dr, dc in zip(DR, DC):
            n_row = cur_row + dr
            n_col = cur_col + dc
            if not (0 <= n_row < H and 0 <= n_col < W):
                continue
            if seen[n_row][n_col]:
                continue
            if A[n_row][n_col] == '
                continue
            q.append((n_row, n_col, num + 1))
            seen[n_row][n_col] = 1
            ans = max(ans, num + 1)
    print(ans)

main()

Solution (Python):
from collections import deque

H, W = list(map(int, input().split()))
field = [[i=='
count = 0

def bfs():
  global count
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x]:
        q.append((y, x))
  while True:
    nq = deque()
    while len(q) > 0:
      y, x = q.popleft()
      for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
          continue
        if field[ny][nx]:
          continue
        field[ny][nx] = True
        nq.append((ny, nx))
    if len(nq) > 0:
      q = nq
    else:
      break
    count += 1
      
bfs()
print(count)

Solution (Python):
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  field = [[i=='
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      if x > 0 and not field[y][x-1]:
        field[y][x-1] = True
        nq.append((y,x-1))
      if y > 0 and not field[y-1][x]:
        field[y-1][x] = True
        nq.append((y-1,x))
      if x<W-1 and not field[y][x+1]:
        field[y][x+1] = True
        nq.append((y,x+1))
      if y<H-1 and not field[y+1][x]:
        field[y+1][x] = True
        nq.append((y+1, x))
    if nq:
      q = copy.copy(nq)
    else:
      break
    count += 1
  print(count)
      
if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  field = [[i=='
  count = 0
  q = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
  while True:
    nq = deque()
    while q:
      y, x = q.popleft()
      if x > 0 and not field[y][x-1]:
        field[y][x-1] = True
        nq.append((y,x-1))
      if y > 0 and not field[y-1][x]:
        field[y-1][x] = True
        nq.append((y-1,x))
      if x<W-1 and not field[y][x+1]:
        field[y][x+1] = True
        nq.append((y,x+1))
      if y<H-1 and not field[y+1][x]:
        field[y+1][x] = True
        nq.append((y+1, x))
    if nq:
      q = copy.copy(nq)
    else:
      break
    count += 1
  print(count)
      
if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque

def bfs(grid, queue, wall, vis, hw):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue and vis < hw:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
            vis += 1
    return ans

H,W = map(int, input().split())
wall = '
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]
cnt = 0

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
            cnt += 1
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall, cnt, H*W))

Solution (Python):
from collections import deque

def bfs(grid, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
    return ans

H,W = map(int, input().split())
wall = '
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall))

Solution (Python):
from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

Solution (Python):



from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()

Solution (Python):
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
A=[[False]*(w+2) for _ in range(h+2)]
chk,chk2=[],[]
for i in range(h):
  s=input()
  for j in range(w):
    A[i+1][j+1]=(s[j]==".")
    if s[j]=="
      chk.append((i+1,j+1))
ans=0
d=((1,0),(0,1),(-1,0),(0,-1))
while chk:
  for cx,cy in chk:
    for dx, dy in d:
      if A[cx+dx][cy+dy]==True:
        chk2.append((cx+dx,cy+dy))
        A[cx+dx][cy+dy]=False
  if chk2:
    ans+=1
  chk=chk2
  chk2=[]
print(ans)

Solution (Python):
from scipy.ndimage import distance_transform_cdt
h,w = map(int, input().split())
grid = [[i=="." for i in input()] for _ in range(h)]
print(distance_transform_cdt(grid, metric='taxicab').max())

Solution (Python):
from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = deque()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "
				nxt.append((i,j,0))
a=0
while nxt:
	i,j,t = nxt.popleft()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w) and grid[i][j] == ".":
				grid[i][j] = "
				nxt.append((i,j,t+1))
print(a)

Solution (Python):


import numpy as np



def main():
    h, w = map(int, input().split())
    max_value = h + w
    gridmap = []

    for y in range(h):
        gridmap.append([0 if v == '

    values = np.array(gridmap)

    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 y in range(h - 1):
        values[y + 1, :] = np.minimum(values[y, :] + 1, values[y + 1, :])

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

    print(np.max(values))


if __name__ == '__main__':
    
    main()

Solution (Python):
from collections import deque

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

dist = [[float("inf")]*W for i in range(H)]
q = deque([])
for y in range(H) :
    for x in range(W) :
        if A[y][x] == "
            dist[y][x] = 0
            q.append((y,x))

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

while q :
    y,x = q.popleft()
    for dy,dx in dxy :
        ny,nx = y+dy,x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W :
            continue
        if dist[ny][nx] > dist[y][x] + 1 :
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

ans = 0
for y in range(H) :
    ans = max(ans, max(dist[y]))
print(ans)

Solution (Python):
from collections import deque


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[-1] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == -1:
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

Solution (Python):
from collections import deque


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[-1] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == -1:
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

Solution (Python):
from collections import deque
 
H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))

Solution (Python):
import numpy
H,W = map(int,input().split())
a_list = []
INF = 10**10
for i in range(H):
    str = input()
    a_list.append([0 if i == "

a_list = numpy.array(a_list)
for x in range(W-1):
    a_list[:,x+1] = numpy.minimum(a_list[:,x]+1,a_list[:,x+1])
    a_list[:,-x-2] = numpy.minimum(a_list[:,-x-1]+1,a_list[:,-x-2])

for y in range(H-1):
    a_list[y+1,:] = numpy.minimum(a_list[y,:]+1,a_list[y+1,:])
    a_list[-y-2,:] = numpy.minimum(a_list[-y-1,:]+1,a_list[-y-2,:])

print(a_list.max())

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

from collections import deque

q=deque([])
B=[[None]*W for _ in range (H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            q.append((i,j))
            B[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while len(q)>0:
  XY=[]
  while len(q)>0:
     XY.append(q.popleft())
  for xy in XY:
    for i in range(4):
      if 0<=(xy[0]+dx[i])<=H-1 and 0<=(xy[1]+dy[i])<=W-1:
        if B[xy[0]+dx[i]][xy[1]+dy[i]]==None:
          B[xy[0]+dx[i]][xy[1]+dy[i]]=B[xy[0]][xy[1]]+1
          q.append((xy[0]+dx[i],xy[1]+dy[i]))
        else: pass
      else: pass
print(max([max(B[i]) for i in range(H)]))

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect


import math
import heapq

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

dist = [[10000000 for i in range(W)] for j in range(H)]

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


while len(now) > 0:
	loc = now.popleft()
	if loc[0] < H - 1 and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] - 1])

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

Solution (Python):
import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)

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

h, w = map(int, input().split())
field = []
todo = deque([])

for y in range(h):
    text = input()
    field.append(text)
    for x in range(w):
        if text[x] == '
            todo.append([y, x])

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

seen = [[None] * w for _ in range(h)]

for y, x in todo:
    seen[y][x] = 0

while todo:
    y, x = todo.popleft()

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]

        if ny < 0 or h <= ny or nx < 0 or w <= nx:
            continue
        elif seen[ny][nx] is not None:
            continue
        else:
            seen[ny][nx] = seen[y][x] + 1
            todo.append([ny, nx])

    if not todo:
        print(seen[y][x])

Solution (Python):
from collections import deque
import sys
def main():
    H,W = list(map(int,sys.stdin.readline().split()))
    place_h = [0,-1,0,1]
    place_w = [1,0,-1,0]
    black = 0
    q = deque([])
    dist = []
    A = []
    for i in range(H):
        a = sys.stdin.readline().split()
        a = list(a[0])
        dist_sub = []
        for j in range(W):
            if a[j] == "
                black += 1
                q.append([i,j])
                dist_sub.append(0)
            else:
                dist_sub.append(-1)
        A.append(a)
        dist.append(dist_sub)

    ans = 0
    
    while len(q) > 0:
        vh,vw = q.popleft()
        for m in range(4):
            nvh = vh+place_h[m]
            nvw = vw+place_w[m]
            if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw] == -1:
                q.append([nvh,nvw])
                dist[nvh][nvw] = dist[vh][vw]+1
                if ans < dist[nvh][nvw]:
                    ans = dist[nvh][nvw]

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

H, W = map(int, input().split())
A = [[] for _ in range(H)]
inf = 10 ** 7
for i in range(H):
    A[i] = list(input())
    for j in range(W):
        if A[i][j] == '.':
            A[i][j] = inf
        elif A[i][j] == '
            A[i][j] = 0

A = np.array(A)



for j in range(1, W):
    A[:,j] = np.minimum(A[:,j-1]+1, A[:,j])


for j in range(W-2, -1, -1):
    A[:,j] = np.minimum(A[:,j+1]+1, A[:,j])



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



for i in range(H-2, -1, -1):
     A[i,:] = np.minimum(A[i+1,:]+1, A[i,:])




ans = np.max(A)




print(ans)

Solution (Python):
from collections import deque
import copy
H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
L=[[0]*W for _ in range(H)]
next_q=deque()

for i in range(H):
    for j in range(W):
        if A[i][j]=='
            L[i][j]=1
            next_q.append((i,j))

q=deque()

res = 0
while len(next_q) != 0:
    q=copy.copy(next_q)
    next_q.clear()
    while q:
        y, x = q.popleft()
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q)==0: break
    res += 1
print(res)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
Q = deque()
INF = H+W+1
C = [[-1]*W for i in range(H)]
for y in range(H):
  for x in range(W):
    if A[y][x] == "
      Q.append((y,x))
      C[y][x] = 0
X = [1,0,-1,0]
Y = [0,-1,0,1]
      
while Q:
  y,x = Q.popleft()
  for i in range(4):
    ny = y + Y[i]
    nx = x + X[i]
    if 0<=ny<H and 0<=nx<W and C[ny][nx]==-1 and A[ny][nx] == ".":
      C[ny][nx] = C[y][x] + 1
      Q.append((ny,nx))
ans = 0
for i in range(H):
  ans = max(ans,max(C[i]))
print(ans)

Solution (Python):
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

data = []

for _ in range(H):
    data.append(list(input()))

searched = [[0]*(W+2)]

for _ in range(H):
    searched.append([0] + [1000000]*W + [0])
searched.append([0]*(W+2))

visit_p = deque()
for h,i in enumerate(data):
    for w, j in enumerate(i):
        if j == "
            searched[h+1][w+1] = 0
            visit_p.append((h+1, w+1, 0))
while visit_p:
    nh,nw,num = visit_p.popleft()
    if searched[nh][nw] < num:
        continue
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        if searched[nh+dh][nw+dw] > num + 1:
            searched[nh+dh][nw+dw] = num + 1
            visit_p.append((nh+dh,nw+dw,num+1))
print(max(map(max, searched)))