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):
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '
visited += [[True] * (W + 2)]
ans = -1
q = []
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if visited[i][j]:
            q.append((i, j))

while q:
    tmp = []
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            tmp.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            tmp.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            tmp.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            tmp.append((h, w + 1))
    q = tmp
    ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
H, W = map(int, input().split())
visited = [[True] * (W + 2)]
visited += [[True] + [x == '
visited.append([True] * (W + 2))

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

ans = -1
while q:
    tmp = []
    ans += 1
    for h, w in q:
        if not visited[h - 1][w]:
            visited[h - 1][w] = True
            tmp.append((h - 1, w))
        if not visited[h + 1][w]:
            visited[h + 1][w] = True
            tmp.append((h + 1, w))
        if not visited[h][w - 1]:
            visited[h][w - 1] = True
            tmp.append((h, w - 1))
        if not visited[h][w + 1]:
            visited[h][w + 1] = True
            tmp.append((h, w + 1))
    q = tmp
print(ans)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
from collections import deque
def main():
    h,w = map(int,input().split())
    grid = []
    dq = deque([])
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    ans = 0
    d = [[-1 for i in range(w)] for j in range(h)]
    for i in range(h):
        maze = list(input())
        for j in range(w):
            if maze[j] == "
                dq.append((j,i))
                d[i][j] = 0
        grid.append(maze)
    while dq:
        x,y = dq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx <= w-1 and 0 <= ny <= h-1 and grid[ny][nx] != "
                dq.append((nx,ny))
                d[ny][nx] = d[y][x] + 1
                ans = max(ans,d[ny][nx])
    print(ans)
main()

Solution (Python):
from collections import deque

dy = (1, 0, -1, 0)
dx = (0, 1, 0, -1)

h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
q = deque()
for y in range(h):
    for x in range(w):
        if table[y][x] == "
            q.append((y, x))
            table[y][x] = 0

while q:
    y, x = q.popleft()
    d = table[y][x]
    for k in range(4):
        ny, nx = y + dy[k], x + dx[k]
        if 0 <= ny < h and 0 <= nx < w:
            if table[ny][nx] == ".":
                table[ny][nx] = d + 1
                q.append((ny, nx))
print(max(list(map(lambda n: max(n), table))))

Solution (Python):
from collections import deque
h,w = map(int,input().split())
grid = []
dq = deque([])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
d = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    maze = list(input())
    for j in range(w):
        if maze[j] == "
            dq.append((j,i))
            d[i][j] = 0
    grid.append(maze)
while dq:
    x,y = dq.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= w-1 and 0 <= ny <= h-1 and grid[ny][nx] != "
            dq.append((nx,ny))
            d[ny][nx] = d[y][x] + 1
            ans = max(ans,d[ny][nx])
print(ans)

Solution (Python):
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "
            for i in range(H)]
checked += [[True]*(W+2)]

black_list = []


for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))


ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Solution (Python):

import numpy as np
from collections import deque

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  
  

  dark_points = [(x + 1, y + 1) for x in range(W) for y in range(H) if grid[y][x] == "

  visited = [[True] * (W + 2)]
  visited += [[True] + [False for x in range(W)] + [True] for y in range(H)]
  visited.append([True for x in range(W + 2)])
  
  
  
  for x, y in dark_points:
    visited[y][x] = True
  
  
  
  
  
  

  
  

  
  

  
  

  
  

  
  

  q = dark_points
  ans = 0
  while len(q) > 0:
    ans += 1
    next_q = []
    for x, y in q:
      if not visited[y - 1][x]: 
        visited[y - 1][x] = ans
        next_q.append((x, y - 1))
      if not visited[y + 1][x]: 
        visited[y + 1][x] = ans
        next_q.append((x, y + 1))
      if not visited[y][x - 1]: 
        visited[y][x - 1] = ans
        next_q.append((x - 1, y))
      if not visited[y][x + 1]: 
        visited[y][x + 1] = ans
        next_q.append((x + 1, y))
      
    
    
    
    
    q = next_q

  print(ans - 1)

if __name__ == "__main__":
  main()

Solution (Python):
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []


for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))


ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Solution (Python):

import numpy as np

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  
  

  
  visited = np.zeros((H, W), int)
  for y in range(H):
    
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

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

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

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

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

  
  

  
  
  
  
  
  print(np.max(visited))

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
def main():
    H,W = map(int, input().split())
    road = [[False]*W for _ in range(H)]
    arrived = [[False]*W for _ in range(H)]
    que = deque([]) 
    origWhite = 0
    for i in range(H):
        c = input()
        for j in range(W):
            if c[j]=='.':
                road[i][j] = True
                origWhite += 1
            else:
                que.append((i,j))
                arrived[i][j] = True

    if origWhite<=0:
        print(0)
        return

    directions = [(1,0),(0,1),(-1,0),(0,-1)] 
    depth = [[0]*W for _ in range(H)]
    while que:
        x1,y1 = que.pop()
        for dx,dy in directions:
            x2,y2 = x1+dx,y1+dy
            
            if x2<0 or H<=x2 or y2<0 or W<=y2:
                continue
            
            if not road[x2][y2]:
                continue
            
            if arrived[x2][y2]:
                continue
            que.appendleft((x2,y2))
            arrived[x2][y2] = True
            origWhite -= 1
            depth[x2][y2] = depth[x1][y1]+1
            if origWhite<=0:
                print(depth[x2][y2])
                return


main()

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

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

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

print(ans)

Solution (Python):
import sys

import math


from collections import deque


input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
while b:
    z=b.popleft()
    i=z[0]
    j=z[1]
    if i<h-1 and n[(i+1)*w+j]==-1:
      n[(i+1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i+1),j))
      f=True
    if i>0  and n[(i-1)*w+j]==-1:
      n[(i-1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i-1),j))
      f=True
    if j<w-1 and n[i*w+(j+1)]==-1:
      f=True
      n[i*w+(j+1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j+1)))
    if j>0  and n[i*w+(j-1)]==-1:
      f=True
      n[i*w+(j-1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j-1)))
   
print(c)

Solution (Python):
import sys

import math


from collections import deque


input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
p = [(1,0),(-1,0),(0,1),(0,-1)]

while b:
    i,j=b.popleft()
    for s,t in p:
      if 0 <= i+s <= h-1 and 0 <= j+t <= w-1:
        if n[(i+s)*w+(j+t)]==-1:
          n[(i+s)*w+(j+t)]=n[i*w+j]+1
          c=max(c,n[i*w+j]+1)
          b.append(((i+s),(j+t)))
    
print(c)

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):
from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if map_input[i][j]=='
            queue.append([j,i])

mx = [0,0,1,-1]
my = [1,-1,0,0]

ans = -1
def bfs(map_input,queue,ans):
    while queue:
        queue2 = deque([])
        ans+=1
        for x,y in queue:
            for i in range(4):
                nx = x+mx[i]
                ny = y+my[i]
                if 0<=nx<w and 0<=ny<h:
                    if map_input[ny][nx]=='
                        continue
                    map_input[ny][nx]='
                    queue2.append([nx,ny])

        queue = queue2
    return ans

ans = bfs(map_input,queue,ans)
print(ans)

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

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

p = [(1,0),(-1,0),(0,1),(0,-1)]
ans = 0
while d:
    x,y = d.popleft()
    for s,t in p:
        if 0 <= x+s <= h-1 and 0 <= y+t <= w-1:
            if visit[x+s][y+t] == -1:
                visit[x+s][y+t] = visit[x][y] + 1
                ans = max(ans,visit[x][y]+1)
                d.append((x+s,y+t))
        
print(ans)

Solution (Python):
from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)

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

ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)

print(ans)

Solution (Python):



from collections import deque



def bfs(h, w, board, start_list, dx, dy):

    
    task_deque = deque()
    
    task_deque.append(start_list)
    next_task_list = deque()
    turn_count = 0

    while task_deque:
        next_task_list.clear()
        task_list = task_deque.popleft()


        
        for x, y in task_list:

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

                
                if 0 <= nx < w and 0 <= ny < h and board[ny][nx] == ".":
                    board[ny][nx] = "
                    next_task_list.append([nx, ny])


        
        if len(next_task_list) == 0:
            return turn_count

        
        turn_count += 1
        lst = []
        for task in next_task_list:
            lst.append(task)
        task_deque.append(lst)



h, w = map(int, input().split())
board = [list(input().rstrip()) for j in range(h)]

start_list = deque()


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


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


print(bfs(h, w, board, start_list, dx, dy))

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(input()))
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=='
            q.append((i, j, 0))
dxdy = [(-1, 0), (0, -1), (0, 1), (1, 0)]
ans = 0
while q:
    y, x, cnt = q.popleft()
    for dx, dy in dxdy:
        if not(0<=x+dx<w and 0<=y+dy<h):
            continue
        if a[y+dy][x+dx]=='.':
            a[y+dy][x+dx] = '
            q.append((y+dy, x+dx, cnt+1))
            ans = cnt+1
print(ans)

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


HW=[ [-1 for w in range(W)] for h in range(H) ]


from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

print(ans)

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

m = [list(input()) for _ in range(h)]

start_points = [(y,x) for y in range(h) for x in range(w) if m[y][x] == '

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for _ in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(start_points))

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

m = [list(input()) for _ in range(h)]

def get_start_points(m):
    start_points = []
    for y in range(h):
        for x in range(w):
            if m[y][x] == '
                start_points.append((y,x))
    return start_points

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for q in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(get_start_points(m)))

Solution (Python):
from collections import deque

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

from collections import deque

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

def bfs(q, a):
  
    ret = deque([])
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if a[ny][nx] == -1:
                    ret.append([nx, ny])
                    a[ny][nx] = 0
    return ret, a
  
q = deque([])

a = [[0 for _ in range(W)] for _ in range(H)]
for i in range(W):
    for j in range(H):
        if A[j][i] == ".":
            a[j][i] = -1  

ans = 0
for i in range(W):
    for j in range(H):
        if a[j][i] == 0:
            q.append([i, j])

ans = -1
while q:
    ans += 1
    q, a = bfs(q, a)
            
print(ans)

Solution (Python):
import sys
from collections import deque
H,W = map(int,sys.stdin.readline().rstrip().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if map[i][j] == '
      q.append((i,j))
      dist[i][j] = 0

def bfs():
  while q:
    x,y = q.popleft()
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<= nx < H and 0 <= ny < W and map[nx][ny] == '.' and dist[nx][ny] == -1:
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))
bfs()
ans = 0
for i in range(H):
  ans = max(max(dist[i][:]),ans)
print(ans)

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

inf = 10**6
d = [[inf]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            q.append((i, j, 0))
            d[i][j] = 0
            
while q:
    temp = q.popleft()
    x = temp[0]
    y = temp[1]
    r = temp[2]
    if x > 0 and d[x-1][y] > r+1:
        d[x-1][y] = r+1
        q.append((x-1, y, r+1))
    if y > 0 and d[x][y-1] > r+1:
        d[x][y-1] = r+1
        q.append((x, y-1, r+1))
    if x < H-1 and d[x+1][y] > r+1:
        d[x+1][y] = r+1
        q.append((x+1, y, r+1))
    if y < W-1 and d[x][y+1] > r+1:
        d[x][y+1] = r+1
        q.append((x, y+1, r+1))

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

Solution (Python):
'''


■考え方
以下を繰り返し、白マスがなくなった時点のカウンターが答え。
1.黒マスに隣接する白マスを黒マスに塗り替える
2.カウンターに+1する

1詳細
1-0.現在の黒マスを全てキューへ入れる
1-1.キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
1-2. 1-1を繰り返し


'''

from collections import deque 



import sys



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


sys.setrecursionlimit(10**7) 
inf = float('inf')

is_debug = True


black_str = '
white_str = '.'

def paint(q,M,h,w):
    '''
    キューから黒マスの位置を取り出し、隣接マスを「黒に塗り、キューへ入れる」
    '''
    out_q = deque()
    
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]
    
    while len(q) > 0:
        
        y, x = q.popleft()

        
        for delta in deltas:
            
            after_y = y+delta[0]
            after_x = x+delta[1]
            
            if after_y < 0 or after_y > h-1 or after_x < 0 or after_x > w-1:
                continue

            if M[after_y][after_x] == white_str:
                M[after_y][after_x] = black_str
                
                out_q.append([after_y,after_x]) 
    
    return out_q


def main():
    '''メイン処理'''

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

    ans = 0
    
    q = deque()

    while True:
        
        
        
        

        
        

        
        if ans == 0:
            for i in range(h):
                for j in range(w):
                    if M[i][j] == black_str:
                        q.append([i,j])
        
        
        q = paint(q,M,h,w)
        
        if len(q) == 0:
            break

        ans += 1

    print(ans)


if __name__ == "__main__":
    
    main()

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)]

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

while p:
    y,x = p.popleft()
    d = dist[y][x]
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.append((y+dy,x+dx))

    
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):
    """
    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):
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        
        self.dist = [[-1]*self.W for i in range(self.H)]
        
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  
        graph.append(_)
    
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    
    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())
m = ["
temp = [[-1]*(w+2) for i in range(h+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq = deque()
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if m[i][j] == "
            dq.append((i,j))
            temp[i][j] = 0
while dq:
    y,x = dq.popleft()
    for i in opt:
        y1 = y+i[0]
        x1 = x+i[1]
        if m[y1][x1] == "." and temp[y1][x1] == -1:
            temp[y1][x1] = temp[y][x]+1
            ans = max(ans,temp[y1][x1])
            dq.append((y1,x1))
print(ans)

Solution (Python):
from collections import deque

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

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

queue = deque([])

ans = 0



for i in range(H):
    s = input()
    for j, ss in enumerate(s):
        if ss =="
            queue.append((i, j))
            grid[i][j] = 0


while queue:
    h, w = queue.popleft()
    for i in [h-1, h+1]:
            if i >= 0 and i < H:
                if grid[i][w] == -1:
                    grid[i][w] = grid[h][w]+1
                    queue.append((i, w))
    for j in [w-1, w+1]:
        if j >= 0 and j < W:
            if grid[h][j] == -1:
                grid[h][j] = grid[h][w]+1
                queue.append((h, j))


print(max([max(b) for b in grid]))

Solution (Python):
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w),dtype=int)

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
            
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,w):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(w-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(np.max(visited))

Solution (Python):
import numpy as np

H,W = map(int,input().split())
use = np.zeros((H,W),dtype=int)
for i in range(H):
    s = input()
    for j,st in enumerate(s):
        if st == ".":
            use[i][j] = 10**9

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

print(np.max(use))

Solution (Python):
import numpy as np

H,W = map(int,input().split())
use = np.zeros((H,W),dtype=int)
for i in range(H):
    s = input()
    for j,st in enumerate(s):
        if st == ".":
            use[i][j] = 10**10
        else:
            use[i][j] = 0

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

print(np.max(use))