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 sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    h,w=map(int,input().split())
    B=[[-1]*w for _ in range(h)]
    ans=0
    que=deque()
    for i in range(h):
        s=input()
        for j,ss in enumerate(s):
            if ss=="
                que.append((i,j))
                B[i][j]=0
    while que:
        qr,qc=que.popleft()
        for r,c in ((qr+1,qc),(qr-1,qc),(qr,qc+1),(qr,qc-1)):
            if r>=0 and r<=h-1 and c>=0 and c<=w-1 and B[r][c]==-1:
                B[r][c]=B[qr][qc]+1
                que.append((r,c))
    print(max([max(b) for b in B]))

if __name__=='__main__':
    main()

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



que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

print(now_d)

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]


ans = 0

que = deque()

num_white = H * W

paint = 0

for i in range(H):
    for j in range(W):
        if field[i][j] == "
            que.append((i, j))
            num_white -= 1

def check(field):
    flag = False
    for i in range(H):
        if "." in field[i]:
            flag = True

    return flag

def one_bsf():
    global paint
    global que
    global ans

    for _ in range(len(que)):
        n = que.popleft()
        ny = n[0]
        nx = n[1]

        for i in range(4):
            nny = ny + dy[i]
            nnx = nx + dx[i]

            if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                continue

            elif field[nny][nnx] == ".":
                field[nny][nnx] = "
                paint += 1
                que.append((nny, nnx))

    ans += 1

while num_white != paint:
    one_bsf()
    
print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    H, W = map(int, rl().split())
    grid = [[] for _ in range(H)]
    que = deque()
    for i in range(H):
        grid[i] = list(rl().rstrip())
        for j in range(W):
            if grid[i][j] == '
                que.append((i, j))
    
    ans = -1
    while que:
        n = len(que)
        for _ in range(n):
            cy, cx = que.popleft()
            for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                ny, nx = cy + dy, cx + dx
                if 0 <= nx < W and 0 <= ny < H:
                    if grid[ny][nx] == '.':
                        grid[ny][nx] = '
                        que.append((ny, nx))
        ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    H,W = LI()
    f = [[0] * W for _ in range(H)]
    q = collections.deque()
    for i in range(H):
        for j,x in enumerate(sys.stdin.readline().rstrip()):
            if x == '
                f[i][j] = 1
                q.append((i,j,0))
    ans = 0
    while q:
        y,x,c = q.popleft()
        ans = max(ans,c)
        for dy,dx in ((0,1),(1,0),(-1,0),(0,-1)):
            if 0 <= x+dx < W and 0 <= y+dy < H:
                if f[y+dy][x+dx] == 0:
                    f[y+dy][x+dx] = 1
                    q.append((y+dy,x+dx,c+1))
    print(ans)

if __name__ == '__main__':
    main()

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

from collections import deque
move=[(0,1),(0,-1),(1,0),(-1,0)]

que=deque([])

for i in range(h):
    for j in range(w):
        if G[i][j]=='
            que.append((i,j,0))

c=0
visit=[[0]*w for _ in range(h)]
while len(que)>0:
    ni,nj,c=que.popleft()
    for di,dj in move:
        mi,mj=ni+di,nj+dj
        if 0<=mi<h and 0<=mj<w and G[mi][mj]=='.' and visit[mi][mj]==0:
            visit[mi][mj]=1
            que.append((mi,mj,c+1))
print(c)

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

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

black_cells = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '
            black_cells.append((i, j))
            dist[i][j] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h_black, w_black = black_cells.popleft()
        d=dist[h_black][w_black]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h_black+dy
            new_w = w_black+dx
            if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

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

Solution (Python):
from collections import deque

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

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

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

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

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

Solution (Python):
from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)

Solution (Python):
from collections import deque


H,W = map(int, input().split())
A = [[str(i) for i in list(input())] for _ 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
dyx = [(1,0), (0,1), (-1,0), (0,-1)]
while q:
    flag = False
    for _ in range(len(q)):
        y,x = q.popleft()
        for dy, dx in dyx:
            ny, nx = y+dy, x+dx
            if not 0 <= ny <= H-1 or not 0 <= nx <= W-1:
                continue
            if A[ny][nx] == ".":
                q.append((ny, nx))
                A[ny][nx] = "
                flag = True
    if flag:
        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 < 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
a,b=map(int,input().split())
List=[]
q=deque([[0,0]])
for i in range(a):
  l=list(input())
  for _ in range(b):
    if l[_]=="
      q.append([i,_])
      l[_]=0
  List.append(l)
q.popleft()
aaa=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while q:
  h,w=q.popleft()
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
        if List[h+x][w+y]>ans:
          ans=List[h+x][w+y]
print(ans)

Solution (Python):

from collections import deque

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


def check(matrix):
    for i in range(len(matrix)):
        matrix[i] = ["
    
    matrix = [["
    
    
    
    
    queue = deque()
    
    for i in range(1,H+1):
        for j in range(1, W+1):
            if matrix[i][j] == "
                queue.append( (i, j) )
    
    
    delta = [(1,0),(-1,0),(0,1),(0,-1)]
    step = -1
    
    while queue:
        step += 1
        
        for _ in range(len(queue)):
            r,c = queue.popleft()
            
            for d in delta:
                next_r = r + d[0]
                next_c = c + d[1]
                
                if matrix[next_r][next_c] == ".":
                    matrix[next_r][next_c] = "
                    queue.append( (next_r, next_c) )


    return step



ans = check(A_list)
print(ans)

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

from collections import deque

lst = deque()

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


def chg(i, j):
    if i < 0 or j < 0 or H <= i or W <= j: return False
    if A[i][j] == '.':
        A[i][j] = '
        return True
    return False


ans = 0
while lst:
    h, w, v = lst.popleft()
    ans = max(v, ans)
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0: continue

            if chg(h + i, w + j):
                lst.append((h + i, w + j, v + 1))
print(ans)

Solution (Python):
from collections import deque

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

dist = [[-1]*w for i in range(h)]

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

def bfs(black, dist):
    d = 0
    while black:
        x, y = black.popleft()
        d = dist[x][y]
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = x + dx
            ny = y + dy
            if not(0 <= nx < h) or not(0 <= ny < w):
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = d+1
                black.append((nx, ny))
    return d

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

Solution (Python):
from collections import deque

row, col = map(int, input().split())
graph = [list(input()) for i in range(row)]

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

seen = deque([])
finished = deque([])

for i in range(row):
  for j in range(col):
    if graph[i][j] == "
      finished.append([i, j])
      
while True:

  while len(finished) > 0:
    v = finished.popleft()
    for j in range(4):
      next_y, next_x = v[0]+dy[j], v[1]+dx[j]
      if not 0 <= next_y < row or not 0 <= next_x < col:
        continue
      if graph[next_y][next_x] == '
        continue 

      graph[next_y][next_x] = "
      seen.append([next_y, next_x])
  
  if len(seen) == 0:
    break
  seen, finished = deque([]), seen
  ans += 1
      
print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
inf = 10 ** 6
a = [[0] * (w + 2)] + [[0] + [inf] * w + [0] for _ in range(h)] + [[0] * (w + 2)]
d = deque()

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

stp = ((0, 1), (0, -1), (1, 0), (-1, 0))
res = 0

while d:
    x, y = d.popleft()
    for k, l in stp:
        nx, ny = x + k, y + l
        if a[x][y] + 1 < a[nx][ny]:
            a[nx][ny] = a[x][y] + 1
            res = max(res, a[nx][ny])
            d.append((nx, ny))
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  h,w=map(int,input().split())
  a=[input() for _ in range(h)]
  seen=[[1]*w for _ in range(h)]
  from collections import deque
  todo=deque([])
  for hi,ai in enumerate(a):
    for wj,aij in enumerate(ai):
      if aij=='
        seen[hi][wj]=0
        todo.append((hi,wj))
  ans=-1
  while todo:
    ans+=1
    next_todo=[]
    for hi,wi in todo:
      if hi>0 and seen[hi-1][wi]:
        next_todo.append((hi-1,wi))
        seen[hi-1][wi]=0
      if hi<h-1 and seen[hi+1][wi]:
        next_todo.append((hi+1,wi))
        seen[hi+1][wi]=0
      if wi>0 and seen[hi][wi-1]:
        next_todo.append((hi,wi-1))
        seen[hi][wi-1]=0
      if wi<w-1 and seen[hi][wi+1]:
        next_todo.append((hi,wi+1))
        seen[hi][wi+1]=0
    todo=next_todo
  print(ans)
if __name__=='__main__':
  main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(dist, black, H, W):
    q = deque(black)

    res = 0
    while q:
        h, w = q.pop()

        for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w] + 1
                    if res < dist[nh][nw]:
                        res = dist[nh][nw]
                    q.appendleft((nh, nw))

    return res


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    black = []
    dist = [[-1] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                black.append((h, w))
                dist[h][w] = 0

    ans = bfs(dist, black, H, W)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w=map(int,input().split())
a=[input() for _ in range(h)]
seen=[[-1]*w for _ in range(h)]
from collections import deque
todo=deque([])
for hi in range(h):
  for wi in range(w):
    if a[hi][wi]=='
      seen[hi][wi]=0
      todo.append((hi,wi,0))
while len(todo)>0:
  hi,wi,i=todo.popleft()
  if hi>0 and seen[hi-1][wi]==-1:
    todo.append((hi-1,wi,i+1))
    seen[hi-1][wi]=i+1
  if hi<h-1 and seen[hi+1][wi]==-1:
    todo.append((hi+1,wi,i+1))
    seen[hi+1][wi]=i+1
  if wi>0 and seen[hi][wi-1]==-1:
    todo.append((hi,wi-1,i+1))
    seen[hi][wi-1]=i+1
  if wi<w-1 and seen[hi][wi+1]==-1:
    todo.append((hi,wi+1,i+1))
    seen[hi][wi+1]=i+1
print(max([max(seeni) for seeni in seen]))

Solution (Python):
from collections import deque
import sys
H,W=map(int,input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)

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

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

dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)):
    h,w=q.popleft()
    
    
    for i in range(4):
        y=h+dy[i]
        x=w+dx[i]
        if (y<0)or(y>=H)or(x<0)or(x>=W):
            continue
        if dist[y][x]==-1:
            dist[y][x]=dist[h][w]+1
            q.append([y,x])
ans=0

for i in range(len(dist)):
    ans=max(ans,max(dist[i]))
print(ans)

Solution (Python):
from scipy import array, ndimage
H, _ = map(int, input().split())
print(ndimage.distance_transform_cdt(array([[c == "." for c in input()] for _ in range(H)], dtype=bool), metric="taxicab").max())

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

ans = [ [ 12345678 for _ in range(w) ] for d in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '
            ans[i][j] = 0

for i in range(h):
    for j in range(1,w):
        ans[i][j] = min(ans[i][j], ans[i][j-1]+1)
    for j in range(w-1-1,-1,-1):
        ans[i][j] = min(ans[i][j],ans[i][j+1]+1)

for j in range(w):
    for i in range(1,h):
        ans[i][j] = min(ans[i][j], ans[i-1][j]+1)
    for i in range(h-1-1,-1,-1):
        ans[i][j] = min(ans[i][j], ans[i+1][j]+1)

ma =-4
for x in ans:
    for y in x:
        ma = max(ma,y)
print(ma)

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]

H,W = inputlist()
graph = [0]*H
for i in range(H):
    graph[i] = list(input())
from collections import deque
que = deque()
seen = [[False]*W for _ in range(H)]
li = []
for x in range(H):
    for y in range(W):
        if graph[x][y] == '
            tp = (x,y)
            li.append(tp)
que.append(li)
dx = [1,0,-1,0]
dy = [0,1,0,-1]
count = 0
while len(que) != 0:
    l = que.popleft()
    lis = []
    for tup in l:
        xa = tup[0]
        ya = tup[1]
        for i in range(4):
            nx = xa + dx[i]
            ny = ya + dy[i]
            if nx >= H or ny >= W or nx < 0 or ny < 0:
                continue
            if graph[nx][ny] == '
                continue
            graph[nx][ny] = '
            lis.append((nx,ny))
    count+=1
    if len(lis) == 0:
        print(count-1)
        exit()
    que.append(lis)

Solution (Python):
from collections import deque


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    num=0
    queue=deque([])
    for i in range(h):
        for j in range(w):
            if A[i][j]=="
                queue.append([i,j])
                color[i][j]="gray"

    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white":
                    D[X][Y]=D[a][b]+1
                    num=max(num,D[X][Y])
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[a][b]="black"

    return num


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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]

def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False


def bfs(que):
    finished = set()
    while que:
        x ,y = que.popleft()
        if y*w+x not in finished:
            finished.add(y*w+x)
            for n_x,n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
                if check(n_y,n_x) and graph[n_y][n_x] > graph[y][x] + 1:
                    graph[n_y][n_x] = graph[y][x] + 1
                    que.append((n_x,n_y))
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "
            graph[i][j] = 0
            que.append((j,i))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Solution (Python):
from collections import deque

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

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

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Solution (Python):

"""
愚直にbfs(queueが無くなるまで)
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0


H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def bfs(lst):
    deq = deque(lst)
    ans = 0
    while deq:
        h,w,now = deq.popleft()
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if maze[h+a][w+b]=="
            else:
                maze[h+a][w+b] = "
                ans = max(ans,now+1)
                deq.append([h+a,w+b,now+1])
    return ans

lst1 = []
for i in range(H):
    for j in range(W):
        if maze[i][j] == "
            lst1.append([i,j,0])

print(bfs(lst1))

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


for i in range(H):
    for j in range(W):
        if A[i][j]==".":
            A[i][j]=float("inf")
        else:
            A[i][j]=0

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

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

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

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

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

Solution (Python):
from collections import deque

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

black_idx = [(h,w) for h in range(H) for w in range(W) if A[h][w] == "

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Solution (Python):
from collections import deque

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

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

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([y+1, x], [y, x+1], [y-1, x], [y, x-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Solution (Python):
from collections import deque

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

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

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
ans = 0

while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1 and distance[y][x] + 1 < distance[new_y][new_x]:
            distance[new_y][new_x] = distance[y][x] + 1
            ans = max(ans, distance[y][x] + 1)
            d.append([new_y, new_x])

print(ans)

Solution (Python):

from collections import deque


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


def bfs(starts):
    moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
    dists = [[-1] * W for _ in range(H)]
    max_dist = 0
    que = deque()
    for start in starts:
        dists[start[0]][start[1]] = 0
        que.append(start)
    while len(que):
        ch, cw = que.popleft()
        for dh, dw in moves:
            nh, nw = ch + dh, cw + dw
            if (    0 <= nh < H 
                and 0 <= nw < W 
                and dists[nh][nw] == -1):
                dists[nh][nw] = dists[ch][cw] + 1
                que.append((nh, nw))
                max_dist = max(max_dist, dists[nh][nw])
    return max_dist


def solve():
    starts = ((i, j) for i in range(H) for j in range(W) if A[i][j] == '
    print(bfs(starts))


solve()

Solution (Python):
from collections import deque

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

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '
            d.append((i, j, 0))
            op[i][j] = 0

while d:
    i, j, step = d.popleft()

    for i2, j2 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if 0 <= i2 < h and 0 <= j2 < w:
            if op[i2][j2] == -1:
                d.append((i2, j2, step+1))
                op[i2][j2] = step + 1

print(max([max(op[i]) for i in range(h)]))

Solution (Python):
from collections import deque
h,w=map(int,input().split())
G=[["
for i in range(1,h+1):
  G[i]=["
X=deque()
Y=deque()
V=[[0]*(w+2) for i in range(h+2)]
V[0]=[0]*(w+2)
for i in range(1,h+1):
  V[i]=[0]+[10**7]*w+[0]
V[h+1]=[0]*(w+2)
for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i][j]=="
      X.append(i)
      Y.append(j)
      V[i][j]=0
XX=[-1,0,0,1]
YY=[0,-1,1,0]
while len(X)!=0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  for i in range(4):
    if V[x+XX[i]][y+YY[i]]==10**7:
      V[x+XX[i]][y+YY[i]]=V[x][y]+1
      X.append(x+XX[i])
      Y.append(y+YY[i])
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]>ans:
      ans=V[i][j]
print(ans)

Solution (Python):
from collections import deque
def gridbfs(grid):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    q = deque()
    for y in range(gridy):
        for x in range(gridx):
            if grid[y][x] == '
                dist[y][x] = 0
                q.append((y,x))

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

H,W = map(int,input().split())
Grid = [input() for _ in range(H)]
d = gridbfs(Grid)
print(max(max(d[i]) for i in range(H)))

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

Solution (Python):
from collections import deque

H, W = map(int, input().split())
A = [[0] * (W + 2)] + [[0] + [H * W] * W + [0] for _ in range(H)] + [[0] * (W + 2)]
que = deque()
for i in range(1, H+1):
    for j, a in enumerate(list(input())):
        if a == '
            A[i][j+1] = 0
            que.append((i, j + 1))

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
res = 0
while que:
    h, w = que.popleft()
    for dh, dw in step:
        nh = h + dh
        nw = w + dw
        if A[h][w] + 1 < A[nh][nw]:
            A[nh][nw] = A[h][w] + 1
            res = max(res, A[nh][nw])
            que.append((nh, nw))
print(res)

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


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


black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '
            black_cells.append((h,w))
            dist[h][w] = 0
def bfs(black_cells, dist):
    """
        BFSを用いて、全マス目を黒くする回数を求める

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

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

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

Solution (Python):
H,W = map(int,input().rstrip().split())
M = [[False for _ in range(W)]for _ in range(H)]
que = []
k = [0,0,0]
counter = 0
for i in range(H):
    S = input()
    for i2 in range(W):
        if S[i2] == "
            M[i][i2] = True
            que.append([i,i2,0])
while counter != H * W:
    k = que[counter]
    if(k[0] + 1 != H and M[k[0] + 1][k[1]] == False):
        M[k[0] + 1][k[1]] = True
        que.append([k[0] + 1,k[1],k[2] + 1])
    if(k[0] - 1 != -1 and M[k[0] - 1][k[1]] == False):
        M[k[0] - 1][k[1]] = True
        que.append([k[0] - 1,k[1],k[2] + 1])
    if(k[1] + 1 != W and M[k[0]][k[1] + 1] == False):
        M[k[0]][k[1] + 1] = True
        que.append([k[0],k[1] + 1,k[2] + 1])
    if(k[1] - 1 != -1 and M[k[0]][k[1] - 1] == False):
        M[k[0]][k[1] - 1] = True
        que.append([k[0],k[1] - 1,k[2] + 1])
    counter += 1
print(k[2])

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 - 2, -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 - 2, -1, -1):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))