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
input = sys.stdin.readline
def main():
  h,w=map(int,input().split())
  a=[list(map(lambda x:0 if x=='
  todo=[]
  from collections import deque
  for i in range(h):
    for j in range(w):
      if a[i][j]==0:
        todo.append([i,j])
  todo=deque(todo)
  ans=0
  while todo:
    i,j=todo.popleft()
    d=a[i][j]+1
    ans=d-1
    if i>0 and a[i-1][j]==-1:
      a[i-1][j]=d
      todo.append([i-1,j])
    if i<h-1 and a[i+1][j]==-1:
      a[i+1][j]=d
      todo.append([i+1,j])
    if j>0 and a[i][j-1]==-1:
      a[i][j-1]=d
      todo.append([i,j-1])
    if j<w-1 and a[i][j+1]==-1:
      a[i][j+1]=d
      todo.append([i,j+1])
  print(ans)
if __name__=='__main__':
  
  
  main()

Solution (Python):
from collections import deque

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

by,bx= deque(),deque()
Map = []
Map.append('@'*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '
      Map[i+1][j] = 0
      by.append(i+1),bx.append(j)
Map.append('@'*(W+2))      

cnt = 0
while(1):
  if(len(by) == 0):
    break
   
  ny,nx = by.popleft(),bx.popleft()
  vec_y,vec_x = [1,-1,0,0],[0,0,1,-1]
  for i in range(4):
      if(Map[ny+vec_y[i]][nx+vec_x[i]] == '.'):
         Map[ny+vec_y[i]][nx+vec_x[i]] = Map[ny][nx] + 1
         cnt = max(cnt, Map[ny][nx] + 1) 
         by.append(ny+vec_y[i]),bx.append(nx+vec_x[i])
  
print(cnt)

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

queue=[]
mat=[[True]*(W+2)]
for i in range(1,H+1):
  array=[True]+[x=="
  mat.append(array)
  for j in range(1,W+1):
    if array[j]:
      queue.append((i,j))
mat.append([True]*(W+2))



d=0
while queue:
  new_queue=set()
  for q in queue:
    i,j=q
    
    if not mat[i-1][j]:
      new_queue.add((i-1,j))
      mat[i-1][j]=True
    if not mat[i+1][j]:
      new_queue.add((i+1,j))
      mat[i+1][j]=True
    if not mat[i][j-1]:
      new_queue.add((i,j-1))
      mat[i][j-1]=True
    if not mat[i][j+1]:
      new_queue.add((i,j+1))
      mat[i][j+1]=True
      
  queue=list(new_queue)
  d+=1
  
print(d-1)

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

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

def bfs(M,dist):
    d=0
    while M:
        x,y=M.popleft()
        d=dist[x][y]
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            new_h=x+dy
            new_w=y+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
                M.append((new_h,new_w))
    return d

d=bfs(M,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 dx, dy 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())
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 dx, dy 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().split())
from sys import stdin
field = []
bque = []
for i in range(H):
    st = stdin.readline()[:-1]
    ls = []
    for j,ss in enumerate(st):
        ls.append(ss)
        if ss=='
            bque.append([i,j])

    field.append(ls)

from collections import deque

que = deque([])
que.append(bque)
count = 0
while len(que)>0:
    ll = que.popleft()
    nls = []
    for item in ll:
        x = item[0]
        y = item[1]
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=x+dx<=H-1:
                    if field[x+dx][y]=='.':
                        field[x+dx][y]='
                        nls.append([x+dx,y])
                if 0<=y+dy<=W-1:
                    if field[x][y+dy]=='.':
                        field[x][y+dy]='
                        nls.append([x,y+dy])
    if len(nls) != 0:
        que.append(nls)
        count += 1
print(count)
"""微妙に遅かった60msぐらい　"""

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


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

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            que.append((i, j))
            seen[i][j] = 0
ans = 0


while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '
            que.append((xi, yi))
    
print(ans)

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

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="
            Bs.append([i,j])

from collections import deque
memo = [[2000] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==2000):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n = map(int, input().split())
    grid = [input() for _ in range(m)]

    Q = deque()
    dist = [[INF] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '
                dist[i][j] = 0
                Q.append((i, j))

    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while Q:
        i, j = Q.popleft()
        for di, dj in D:
            ni, nj = i + di, j + dj
            if not (0 <= ni < m and 0 <= nj < n):
                continue
            if dist[ni][nj] != INF:
                continue
            dist[ni][nj] = dist[i][j] + 1
            Q.append((ni, nj))


    print(max(dist[i][j] for i in range(m) for j in range(n)))
resolve()

Solution (Python):
import numpy as np

def main():
    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))

if __name__ == "__main__":
    main()

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
s = [None] * h
for i in range(h):
    s[i] = input()

r = h
c = w
ds = [[10**15]*c for _ in range(r)]
for i in range(r):
    prev = -1
    for j in range(c):
        if s[i][j]=="
            prev = j
        if prev>=0:
            ds[i][j] = j-prev
    prev = -1
    for j in range(c-1,-1,-1):
        if s[i][j]=="
            prev = j
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev-j)
for j in range(c):
    prev = -1
    prevind = -1
    for i in range(r):
        if prev<0 or ds[i][j]<prev+(i-prevind):
            prev = ds[i][j]
            prevind = i
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev+(i-prevind))
    prev = -1
    prevind = -1
    for i in range(r-1, -1, -1):
        if prev<0 or ds[i][j]<prev+(prevind-i):
            prev = ds[i][j]
            prevind = i
        if prev>=0:
            ds[i][j] = min(ds[i][j], prev+(prevind-i))
print(max(max(item) for item in ds))

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
a = [list(input())[: -1] for _ in range(H)]
dist = [[H * W] * W for _ in range(H)]
Q = dq([])
for i in range(H):
  for j in range(W):
    if a[i][j] == "
      Q.append((i, j))
      dist[i][j] = 0

d = [-1, 0, 1, 0]
while len(Q):
  y, x = Q.popleft()
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if dist[u][v] > dist[y][x] + 1:
        dist[u][v] = dist[y][x] + 1
        Q.append((u, v))
print(max([max(dist[i]) for i in range(H)]))

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
Q = deque()
h = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            Q.append([i, j])
        else:
            h += 1
Qtmp = deque()

yudrl = [0, 1, 0, -1]
xudrl = [1, 0, -1, 0]

c = 0
while h > 0:
    c += 1
    while len(Q) > 0:
        Qtmp.append(Q.pop())
    while len(Qtmp) > 0:
        q = Qtmp.pop()

        for i in range(4):
            y = q[0] + yudrl[i]
            x = q[1] + xudrl[i]

            if y < 0 or y > H - 1 or x < 0 or x > W - 1:
                continue
            if A[y][x] == '
                continue
            A[y][x] = '
            h -= 1
            Q.append([y, x])
print(c)

Solution (Python):
import collections
INF = 10**18
h,w = map(int,input().split())
li = [list(input()) for i in range(h)]
koho = []
d = [[-1]*w for i in range(h)]
q = collections.deque([])
for i in range(h):
    for j in range(w):
        if li[i][j] == "
            d[i][j] = 0
            q.append([i,j])
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while q:
    p = q.popleft()
    y = p[0]
    x = p[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<w and 0<=ny<h:
            if d[ny][nx] == -1:
                q.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans,d[i][j])
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            queue.append([nh, nw])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dist[i][j])
print(ans)

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

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            u[i-1][j]='
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            u[i+1][j]='
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            u[i][j-1]='
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            u[i][j+1]='
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

z=[]
for b in dist:
    z.append(max(b))

print(max(z))

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
def main():
    
    def input():
        return sys.stdin.readline()[:-1]
    def ruiseki(lst):
        return [0]+list(accumulate(lst))
    mod=pow(10,9)+7
    al=[chr(ord('a') + i) for i in range(26)]
    direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

    cnt=0

    itta=[[10**9]*w for i in range(h)]

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

    
    

    while d:
        cnt+=1
        for l in range(len(d)):
            nh,nw=d.popleft()
            for i in range(4):
                d1,d2=direction[i]
                if 0<=nh+d1<h and 0<=nw+d2<w:
                    if itta[nh+d1][nw+d2]==10**9:
                        itta[nh+d1][nw+d2]=cnt
                        d.append((nh+d1,nw+d2))
        

    
    print(cnt-1)

if __name__ == '__main__':
    main()

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

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

d = [[-1] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

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

ans = 0
while que:
  p = que.popleft()
  for i in range(4):
      nw = p[1] + dx[i]
      nh = p[0] + dy[i]
      if 0 <= nw < w and 0 <= nh < h and d[nh][nw]==-1:
          que.append((nh,nw,p[2]+1))
          d[nh][nw] = p[2]+1
          ans = max(ans,p[2]+1)

print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

d=deque()

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




while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    d.append((nh+d1,nw+d2))
    


print(cnt-1)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

d=deque()

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




while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    d.append([nh+d1,nw+d2])
    


print(cnt-1)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

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




while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    aaa([nh+d1,nw+d2])
    


print(cnt-1)

Solution (Python):
from collections import deque

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

Map = [[-1] * W for i in range(H)]

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

ans = 0
while d:
  x, y = d.popleft()
  dist = Map[x][y]
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    u, v = x + dx, y + dy
    if 0<=u<H and 0<=v<W and Map[u][v]==-1:
      Map[u][v] = dist + 1
      ans = max(ans, dist + 1)
      d.append([u, v])

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

def agc033_a():
    H, W = map(int, readline().split())
    dist = [[-1] * W for _ in range(H)]
    que = deque()
    for i, ln in enumerate(read().split()):
        for j, c in enumerate(ln.strip().decode('UTF-8')):
            if c == '
                que.append((i, j))
                dist[i][j] = 0

    while que:
        x, y = que.popleft()
        for i, j in ((x-1, y), (x, y-1), (x, y+1), (x+1, y)):
            if i < 0 or H-1 < i or j < 0 or W-1 < j: continue
            if dist[i][j] != -1: continue
            dist[i][j] = dist[x][y] + 1
            que.append((i, j))

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

agc033_a()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
a = [input() for _ in range(h)]
que = deque([])
dst = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            que.append([i, j])
            dst[i][j] = 0

max_d = 0
while que:
    y, x = que.popleft()
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        if a[ny][nx] == '
            continue
        if dst[ny][nx] != -1:
            continue

        dst[ny][nx] = dst[y][x] + 1
        max_d = dst[y][x] + 1
        que.append([ny, nx])
print(max_d)

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

arr = ["0" *(w + 2)]
for i in range(h):
    arr.append("0" + input() + "0")
arr.append("0" *(w + 2))

flg = [[-1 for i in range(w+2)] for j in range(h+2)]

ima = []
for i in range(h+2):
    for j in range(w+2):
        if arr[i][j] == "
            ima.append([i,j])
            flg[i][j] = 0

while len(ima) > 0:
    tugi = []
    for x,y in ima:
        if arr[x+1][y] == "." and flg[x+1][y] == -1:
            tugi.append([x+1,y])         
            flg[x+1][y] = flg[x][y] + 1
        if arr[x-1][y] == "." and flg[x-1][y] == -1:
            tugi.append([x-1,y])
            flg[x-1][y] = flg[x][y] + 1
        if arr[x][y+1] == "." and flg[x][y+1] == -1:
            tugi.append([x,y+1])
            flg[x][y+1] = flg[x][y] + 1
        if arr[x][y-1] == "." and flg[x][y-1] == -1:
            tugi.append([x,y-1])
            flg[x][y-1] = flg[x][y] + 1
    ima = tugi

ans = -1
for i in flg:
    for j in i:
        if ans < j:
            ans = j
print(ans)

Solution (Python):

from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

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

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

print(ans)

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

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now_x,now_y = q.popleft()
    ans = dist[now_x][now_y]
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now_x + x
        next_y = now_y + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = ans + 1

print(ans)

Solution (Python):
from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[-1] * W for _ in range(H)]

ans = 0
que = deque([])
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            visited[i][j] = 0
            for di, dj in move:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W \
                   and S[ni][nj] != '
                    que.append((ni, nj, 1))
                    visited[ni][nj] = 1
                    ans = 1

while que:
    i, j, d = que.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == -1:
            que.append((ni, nj, d+1))
            visited[ni][nj] = d+1
            ans = d+1

print(ans)

Solution (Python):
from collections import deque

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

as_ = []
for i in range(h):
    a = [s for s in input().split()]
    for a_ in a:
        as_.append(a_)

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


starts = deque()
for i, a in enumerate(as_):
    for j, a_ in enumerate(a):
        if a_ == "
            ds[i][j] = 0
            starts.append((i,j))
def bfs(starts, ds):
    d = 0
    while starts:
        i, j = starts.popleft()
        d = ds[i][j]
        for mx, my in [(0,1),(1,0),(-1,0),(0,-1)]:
            ni = i + my
            nj = j + mx
            if 0 <= ni < h and 0 <= nj < w:
                if ds[ni][nj] == None:
                    ds[ni][nj] = d + 1
                    starts.append((ni, nj))
    return d
d = bfs(starts, ds)
print(d)

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

    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '
                q.append((h,w))
    
    q.append((-1,-1))
    ans = 0
    while len(q) > 0:
        h,w = q.popleft()
        if h == -1 and w == -1:
            if len(q) > 0:
                q.append((-1,-1))
                ans += 1
            continue

        d = ((0,1),(0,-1),(1,0),(-1,0))
        for dh, dw in d:
            if 0 <= h+dh < H and 0 <= w+dw < W and A[h+dh][w+dw] == '.':
                A[h+dh][w+dw] = '
                q.append((h+dh,w+dw))
    print(ans)

if __name__ == '__main__':
    solve()

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(maze, H, W):
    visited = [[-1] * W for _ in range(H)]
    q = deque([])
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "
                visited[h][w] = 0
                q.append((h, w))

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

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

    return res


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = bfs(S, H, W)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):




def input_int():
    return int(input())



def int1(x):
    return int(x) - 1



def input_to_int_map():
    return map(int, input().split())



def input_to_int_tuple():
    return tuple(map(int, input().split()))



def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, w = input_to_int_map()
    zone = [input() for i in range(h)]

    from collections import deque
    black_cell = deque()

    black_distance = [[-1] * w for i in range(h)]
    for i, row in enumerate(zone):
        for j, cell in enumerate(row):
            if cell == "
                black_cell.append((i, j))
                black_distance[i][j] = 0

    while black_cell:
        black_h, black_w = black_cell.popleft()
        pre_black_distance = black_distance[black_h][black_w]
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            move_h = black_h + i
            move_w = black_w + j
            if move_h < 0 or move_w < 0 or move_h >= h or move_w >= w:
                continue
            if black_distance[move_h][move_w] == -1:
                black_distance[move_h][move_w] = pre_black_distance + 1
                black_cell.append((move_h, move_w))

    return max(list(map(max, black_distance)))


if __name__ == "__main__":
    print(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)]


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().split())
maze = []
for _ in range(h):
    maze.append(list(input()))
import collections
black = collections.deque([])
cnt = 0
for hh in range(h):
    for ww in range(w):
        if maze[hh][ww] == "
            cnt += 1
            black.append([hh, ww, 0])
dh = [ 0, -1, 1, 0]
dw = [ -1, 0, 0, 1]
res = 0
allcount = h*w
res = 0
while cnt < allcount:
    
    bh, bw , bturn= black.popleft()
    
    for di in range(len(dh)):
        nh = bh + dh[di]
        nw = bw + dw[di]
        if nh < 0 or nh > (h-1) or nw < 0 or nw > (w-1):
            continue
        if maze[nh][nw] == "
            continue
        black.append([nh, nw, bturn+1])
        
        maze[nh][nw] = "
        res = max(res, bturn+1)
        cnt += 1
print(res)

Solution (Python):
from collections import deque

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

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

    for ni, nj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if i + ni < 0 or j + nj < 0: continue
        if i + ni >= h or j + nj >= w: continue

        if G[i + ni][j + nj] == '.':
            G[i + ni][j + nj] = '
            que.append((i + ni, j + nj, c + 1))
            cnt = max(cnt, c + 1)
print(cnt)

Solution (Python):
from subprocess import *
call(('pypy3','-c',"""
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()
"""))