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, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
dis = [[inf] * w for i in range(h)]
import heapq
def bfs(start_set):
  que = collections.deque()
  for si,sj in start_set:
    que.append((0,si,sj))
    dis[si][sj] = 0
  while que:
    cost,i,j =que.popleft()
    if dis[i][j] < cost: continue
    for di,dj in dydx4:
      ni = i + di
      nj = j + dj
      if not (0 <= ni < h and 0 <= nj < w):continue
      if A[ni][nj] == "
      
      
      
      if cost + 1 < dis[ni][nj]: 
        dis[ni][nj] = cost+1
        que.append((cost+1,ni,nj))

start_set = []
for i in range(h):
  for j in range(w):
    if A[i][j] == "
      start_set.append((i,j))
bfs(start_set)
      
print(max(map(max,dis)))

Solution (Python):
from collections import deque

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

minDist = [[10**10] * W for _ in range(H)]
que = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '
            que.append((h, w, 0))
            minDist[h][w] = 0

while que:
    h, w, d = que.popleft()

    if minDist[h][w] < d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            if minDist[dh + h][dw + w] > d + 1:
                que.append((dh + h, dw + w, d + 1))
                minDist[dh + h][dw + w] = d + 1

ans = max(max(d) for d in minDist)
print(ans)

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

A = [str(input()) for _ in range(h)]

from collections import deque
q = deque()
visit = [[-1]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if A[i][j] == '
            visit[i][j] = 0
            q.append((i, j))

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 0 <= ny <= h-1 and 0 <= nx <= w-1 and visit[ny][nx] == -1:
            visit[ny][nx] = visit[y][x]+1
            q.append((ny, nx))

max_ = -1
for i in range(h):
    for j in range(w):
        max_ = max(visit[i][j], max_)
print(max_)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

h, w = MAP()
a = [STR() for _ in range(h)]
b = [[inf for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if a[i][j] == '
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
ans = 0
for i in range(h):
    ans = max(ans, max(b[i]))
print(ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
a = []
d = []
que = deque()
for i in range(h):
    a.append(list(input()))
    d.append([1e100]*w)
    for j in range(w):
        if a[i][j] == '
            que.append([i,j])
            d[i][j] = 0
di = [-1,0,1,0]
dj = [0,1,0,-1]
ans = 0

while que:
    i,j = que.popleft()
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and d[ni][nj] == 1e100:
            d[ni][nj] = d[i][j] + 1
            ans = max(ans, d[ni][nj])
            que.append([ni,nj])
print(ans)

Solution (Python):


from collections import deque


H, W = map(int,input().split()) 
graph = [input() for i in range(H)]
dist = [[-1]*W for i in range(H)]
que = deque()


for h in range(H):
    for w in range(W):
        if graph[h][w] == "
            que.append([h, w])
            dist[h][w] = 0 
            
def bfs(que, dist):
    cnt = 0 
    while que:
        y, x = que.popleft()
        cnt = dist[y][x] 
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
                continue
            elif dist[new_y][new_x] == -1:
                dist[new_y][new_x] = cnt+1 
                que.append([new_y, new_x]) 
    return cnt 

print(bfs(que,dist))

Solution (Python):
from collections import deque
H, W = map(int, input().split())
gridgraph = [list(input()) for _ in range(H)]
distance = [[50000]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "
            q.append([i, j])
            distance[i][j] = 0
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if distance[ny][nx] != 50000:
            continue
        distance[ny][nx] = distance[cy][cx] + 1
        q.append([ny, nx])
ans = 0
for d in distance:
    ans = max(ans, max(d))
print(ans)

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

def main():
    H, W = map(int, input().split())

    m = [list(map(lambda x: 1 if x=="
    black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]

    
    

    queue = deque(black)
    queue_append = queue.append
    ans = 0
    while queue:
        p = queue.popleft()
        if ans < p[2]:
            ans += 1
        for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    queue_append((next_p[0], next_p[1], ans+1))
    print(ans)

if __name__ == "__main__":
    main()

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

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

m = [list(map(lambda x: 1 if x=="
black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]




queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue_append((next_p[0], next_p[1], ans+1))
print(ans)

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

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

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    
    for j, c in enumerate(input()):
        if c == "
            m[i][j] = 1
            black.append((i, j, 0))




queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        i_next_p, j_next_p = (p[0] + i, p[1] + j)
        if (0 <= i_next_p < H) and (0 <= j_next_p < W):
            if not m[i_next_p][j_next_p]:
                m[i_next_p][j_next_p] = 1
                queue_append((i_next_p, j_next_p, ans+1))
print(ans)

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

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

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    
    for j, c in enumerate(input()):
        if c == "
            m[i][j] = 1
            black.append((i, j, 0))




queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue_append((next_p[0], next_p[1], ans+1))
print(ans)

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

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

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    
    for j, c in enumerate(input()):
        if c == "
            m[i][j] = 1
            black.append((i, j, 0))




queue = deque(black)
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue.append((next_p[0], next_p[1], ans+1))
print(ans)

Solution (Python):
import numpy as np

def main():
  H,W = map(int,input().split())
  maze = [list(input())for _ in range(H)]
  for i in range(H):
    for j in range(W):
      if maze[i][j]=="
        maze[i][j]=0
      else:
        maze[i][j]=float('INF')
  maze = np.array(maze)
  for i in range(1,H):
    maze[i,:]=np.minimum(maze[i,:],maze[i-1,:]+1)
  for i in range(H-2,-1,-1):
    maze[i,:]=np.minimum(maze[i,:],maze[i+1,:]+1)
  for i in range(1,W):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i-1]+1)
  for i in range(W-2,-1,-1):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
  print(int(np.max(maze)))
main()

Solution (Python):



from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for i in range(h):
    for j, c in enumerate(list(input().strip())):
      if c == '
        grids[i*w + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Solution (Python):
import numpy
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
INF = H * W
S = numpy.array([[INF if i == '.' else 0 for i in input().strip()] for _ in range(H)])

for h in range(1, H):
    S[h, :] = numpy.minimum(S[h,:],S[h-1,:] + 1)
for h in range(H - 2, -1, -1):
    S[h, :] = numpy.minimum(S[h,:],S[h+1,:] + 1)
for w in range(1, W):
    S[:, w] = numpy.minimum(S[:,w],S[:,w-1] + 1)
for w in range(W - 2, -1, -1):
    S[:, w] = numpy.minimum(S[:,w],S[:,w+1] + 1)

print(numpy.max(S))

Solution (Python):
from collections import deque

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

for y in range(H):
    for x, v in enumerate(input()):
        if v == '
            data.append((y, x))

ans = [[-1 for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

"""
BFSまとめ

0. 
現在位置、履歴、アクション数の3要素が必要.
処理をLIFOでなく、FIFOでやる
そのため、collection.dequeを使う
更にソートしつつ、FIFOしたい場合は、heapqを使う

1. 
更新する, アクション数を加算する

2. 
条件を一致しているか、履歴に入っていないかを確認

3. 
popをループ
"""

d = 0
while len(data):
    y, x = data.popleft()
    d = ans[y][x]

    for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        new_y = y + i
        new_x = x + j
        if new_y < 0 or H <= new_y or new_x < 0 or W <= new_x:
            continue
        if ans[new_y][new_x] == -1:
            ans[new_y][new_x] = d + 1
            data.append((new_y, new_x))

print(max([a for aa in ans for a in aa]))

Solution (Python):
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    
    for j, c in enumerate(input()):
        if c == "
            m[i][j] = 1
            root.append((i, j))




queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)

Solution (Python):
import numpy as np

def main():
  H,W = map(int,input().split())
  maze = np.array([[0 if x == "
  for i in range(1,H):
    maze[i,:]=np.minimum(maze[i,:],maze[i-1,:]+1)
  for i in range(H-2,-1,-1):
    maze[i,:]=np.minimum(maze[i,:],maze[i+1,:]+1)
  for i in range(1,W):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i-1]+1)
  for i in range(W-2,-1,-1):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
  print(int(np.max(maze)))

main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


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

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

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

    return cnt


h,w=map(int,input().split())
A=[["
A.insert(0,["
A.append(["
print(BFS())

Solution (Python):
import numpy as np
h,w=map(int,input().split())
maze = []
for i in range(h):
  maze.append([0 if x=="
maze = np.array(maze)

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


print(int(np.max(maze)))

Solution (Python):
DX = [0,0,-1,1]
DY = [-1,1,0,0]

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 = 0
while q:
    qq = []

    
    for y,x in q:
        for dy,dx in zip(DY,DX):
            if not visited[y+dy][x+dx]:
                visited[y+dy][x+dx] = True
                qq.append((y+dy,x+dx))

    if not qq:
        break
    
    ans += 1
    q = qq

print(ans)

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

def main():
    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:
        qq = []
        
        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
        ans += 1
    
    print(ans)

if __name__ == '__main__':
    main()

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

r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
dist = [-1]*N
que = deque()
for i in range(r):
    for j in range(c):
        if s[i][j] == '
            que.append(i*c+j)
            dist[i*c+j] = 0


while que:
    v = que.popleft()
    d = dist[v]
    for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
        if 0 <= v//c+y <= r-1 and 0 <= (v % c)+x <= c-1:
            w = v+y*c+x
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)

ans = max(dist)
print(ans)

Solution (Python):
from scipy import ndimage
import numpy as np
h,w = map(int, input().split())
arr = np.array([[0 if s == "
b = ndimage.morphology.distance_transform_cdt(arr,metric="taxicab")
print(b.max())

Solution (Python):
h,w = [int(x) for x in input().split()]
meiro = [list(input()) for _ in range(h)]
ans = [[float("INF")]*w for _ in range(h)]
mina=-1
for i in range(h):
    for j in range(w):
        if meiro[i][j]=="
            ans[i][j]=0
        else:
            if j!=0:
                ans[i][j]=min(ans[i][j-1]+1,ans[i][j])
for i in range(h):
    for j in range(w-1,-1,-1):
        if meiro[i][j]=="
            ans[i][j]=0
        else:
            if j!=w-1:
                ans[i][j]=min(ans[i][j+1]+1,ans[i][j])
for j in range(w):
    for i in range(h):
        if meiro[i][j]=="
            ans[i][j]=0
        else:
            if i!=0:
                ans[i][j]=min(ans[i-1][j]+1,ans[i][j])
for j in range(w):
    for i in range(h-1,-1,-1):
        if meiro[i][j]=="
            ans[i][j]=0
        else:
            if i!=h-1:
                ans[i][j]=min(ans[i+1][j]+1,ans[i][j])
for i in range(h):
    for j in range(w):
        mina = max(mina,ans[i][j])
print(mina)

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

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
B = [[-1 for j in range(W)] for i in range(H)]
que = deque([])
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            B[i][j] = 0
            que.append((i,j,0))
bmax = 0
while que:
    i,j,d = que.popleft()
    bmax = max(bmax,d)
    if j+1<W and B[i][j+1]<0:
        B[i][j+1] = d+1
        que.append((i,j+1,d+1))
    if i-1>=0 and B[i-1][j]<0:
        B[i-1][j] = d+1
        que.append((i-1,j,d+1))
    if j-1>=0 and B[i][j-1]<0:
        B[i][j-1] = d+1
        que.append((i,j-1,d+1))
    if i+1<H and B[i+1][j]<0:
        B[i+1][j] = d+1
        que.append((i+1,j,d+1))
print(bmax)

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

    H, W = map(int, input().split())
    edge = ['
    field = [edge]
    q = deque()

    for i in range(H):
        line = input()
        field.append(['
        for j in range(W):
            if line[j] == '
                q.append((i + 1, j + 1, 0))
    field.append(edge)
    res = 0

    while q:
        y, x, lv = q.popleft()
        if lv > res:
            res = lv

        if field[y + 1][x] == '.':
            field[y + 1][x] = '
            q.append((y + 1, x, lv + 1))

        if field[y - 1][x] == '.':
            field[y - 1][x] = '
            q.append((y - 1, x, lv + 1))

        if field[y][x + 1] == '.':
            field[y][x + 1] = '
            q.append((y, x + 1, lv + 1))

        if field[y][x - 1] == '.':
            field[y][x - 1] = '
            q.append((y, x - 1, lv + 1))

    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=deque([])
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.appendleft([new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)

Solution (Python):
import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def f():
    q = collections.deque()
    dist = [[float("inf")] * W for _ in range(H)]
    for i in range(H):
        for k in range(W):
            if S[i][k] == '
                q.append((i,k))
                dist[i][k] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
dist = f()
for i in range(H):
    for k in range(W):
        ans = max(ans,dist[i][k])
print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
Black = deque([])
Black_grid = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '
            Black.append([j,i])
            Black_grid[i][j] = 0

Move = [[-1,0],[1,0],[0,-1],[0,1]]

while Black:
    now = Black.popleft()
    x = now[0]
    y = now[1]
    for move in Move:
        x_next = x + move[0]
        y_next = y + move[1]
        if x_next < 0 or x_next >= w or y_next < 0 or y_next >= h:
            continue
        elif Black_grid[y_next][x_next] >= 0:
            continue
        else:
            Black.append([x_next, y_next])
            Black_grid[y_next][x_next] = Black_grid[y][x] + 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, Black_grid[i][j])
    
print(ans)

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



from collections import deque
def bfs():
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    log=[[-1]*w for i in range(h)]

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

    while que:
        
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if log[nx][ny]!=-1:continue
            que.append((nx,ny))
            log[nx][ny]=log[p[0]][p[1]]+1

    return log

G=bfs()
ans=0
for i in range(h):
    for j in range(w):
        if ans<G[i][j]:
            ans=G[i][j]
print(ans)

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



from collections import deque
def bfs():
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    log=[[0]*w for i in range(h)]

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

    while que:
        
        p=que.popleft()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]

            if not(0<=nx<h and 0<=ny<w):continue
            if a[nx][ny]=='
            que.append((nx,ny))
            log[nx][ny]=log[p[0]][p[1]]+1
            a[nx][ny]='

    return log

G=bfs()
ans=0
for i in range(h):
    for j in range(w):
        if ans<G[i][j]:
            ans=G[i][j]
print(ans)

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

    H, W = map(int, input().split())
    edge = ['
    field = [edge]
    q = deque()

    for i in range(H):
        line = input()
        field.append(['
        for j in range(W):
            if line[j] == '
                q.append((i + 1, j + 1, 0))
    field.append(edge)
    res = 0

    while q:
        y, x, lv = q.popleft()
        if lv > res:
            res = lv

        if field[y + 1][x] == '.':
            field[y + 1][x] = '
            q.append((y + 1, x, lv + 1))

        if field[y - 1][x] == '.':
            field[y - 1][x] = '
            q.append((y - 1, x, lv + 1))

        if field[y][x + 1] == '.':
            field[y][x + 1] = '
            q.append((y, x + 1, lv + 1))

        if field[y][x - 1] == '.':
            field[y][x - 1] = '
            q.append((y, x - 1, lv + 1))

    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['
field = [edge]
q = deque()

for i in range(H):
    field.append(['
    for j in range(W):
        if field[i+1][j+1] == '
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '
            q.append((y+dy, x+dx, lv+1))

print(res)

Solution (Python):

import sys



def solve(H: int, W: int, A: "List[str]"):
    current = set()
    for i in range(H):
        for j in range(W):
            if not A[i][j]:
                current.add((i,j))
    def appendIfPossible(i,j,s):
        if i >= 0 and i < H and j >=0 and j < W and A[i][j]:
            s.add((i,j))
            A[i][j] = False
    count = 0
    while True:
        next = set()
        for c in current:
            appendIfPossible(c[0]-1,c[1],next)
            appendIfPossible(c[0]+1,c[1],next)
            appendIfPossible(c[0],c[1]-1,next)
            appendIfPossible(c[0],c[1]+1,next)
        current = next
        count+= 1
        if len(next) == 0:
            break
    print(count-1)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    A = [list(map(lambda x:x=='.',next(tokens))) for _ in range(H)]  
    solve(H, W, A)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        a = input()
        A.append(a)
    bl = []
    wl = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                bl.append((i, j))
            else:
                wl.add((i, j))
    r = 0
    while wl:
        bln = []
        for i in bl:
            if (i[0] + 1, i[1]) in wl:
                wl.remove((i[0] + 1, i[1]))
                bln.append((i[0] + 1, i[1]))
            if (i[0] - 1, i[1]) in wl:
                wl.remove((i[0] - 1, i[1]))
                bln.append((i[0] - 1, i[1]))
            if (i[0], i[1] + 1) in wl:
                wl.remove((i[0], i[1] + 1))
                bln.append((i[0], i[1] + 1))
            if (i[0], i[1] - 1) in wl:
                wl.remove((i[0], i[1] - 1))
                bln.append((i[0], i[1] - 1))
        bl = bln
        r += 1
    return r
print(main())

Solution (Python):
def main():
    H, W = list(map(int, input().split()))
    A = [[i for i in input()] for _ in range(H)]
    cur = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                cur.append((h, w))
    r = 0
    while cur:
        nxt = []
        for ch, cw in cur:
            for x, y in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                nh, nw = ch + x, cw + y
                if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                    A[nh][nw] = '
                    nxt.append((nh, nw))
        cur = nxt
        r += 1
    return r - 1

print(main())

Solution (Python):
import copy

def bfs(x, y):
    global tmp
    global cnt
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == ".":
            tmp.append((nx, ny))
            maze[nx][ny] = "
            cnt += 1
    return tmp

h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
ans = 0
cnt = 0
tmp = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
            tmp.append((i, j))
            cnt += 1

while cnt < h * w:
    tmp_ = copy.copy(tmp)
    tmp = []
    while tmp_:
        p = tmp_.pop()
        bfs(p[0], p[1])
    ans += 1
print(ans)