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

c = []
for i in range(H):
    c.append(input())

fresh = [True] * (H*W)



queue = []
n = []
for i in range(H):
    for j in range(W):
        if(c[i][j] == '
            fresh[i*W+j] = False
            queue.append(i*W+j)




step = 0
status = True
while status:
    if(len(queue)>0):
        
        pivot = queue.pop()
        
        
        if(pivot%W != W-1 and fresh[pivot+1]):
            n.append(pivot+1)
            fresh[pivot+1] = False
        
        if(pivot%W != 0 and fresh[pivot-1]):
            n.append(pivot-1)
            fresh[pivot-1] = False
        
        if( int(pivot/W)<(H-1) and fresh[pivot+W]):
            n.append(pivot+W)
            fresh[pivot+W] = False
        
        if( int(pivot/W)>0 and fresh[pivot-W] ):
            n.append(pivot-W)
            fresh[pivot-W] = False
        
    elif(len(n)>0):
        queue = n
        n = []
        
        step += 1
        
    else:
        status = False


print(step)

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



moji = [[0 for i in range(w)] for j in range(h)]

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

for i in range(h):
    aij = input()
    
    for j in range(w):
        moji[i][j] = aij[j]






vx = [0,1,0,-1]
vy = [1,0,-1,0]

ans = 0
q = deque()

for i in range(h*w):
    y = i//w
    x = i%w
    
    if moji[y][x] == '
        q.append(i)
        dist[y][x] = 0



ans = 0

while q:
    
    tmp = q.popleft()
    y = tmp//w
    x = tmp%w
    d = dist[y][x]
    
    for j in range(4):
        nx = x+vx[j]
        ny = y+vy[j]
        
        if nx < 0 or nx >= w or ny < 0 or ny >= h:
            continue
        if dist[ny][nx] == -1:
            dist[ny][nx] = d+1
            
            q.append(ny*w+nx)
    
    ans = max(d,ans)

print(ans)

Solution (Python):
from collections import deque
 
h,w = map(int,input().split())
s = [None]*h
 
for i in range(h):
    s[i] = input()
 
d = [[10000000 for i in range(w)] for j in range(h)]
sharp = 0
 
sx = []
sy = []
            
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            sx.append(j)
            sy.append(i)
            d[i][j] = 0
            
            
def bfs():
    que = deque()
    ans = 0
    for i in range(len(sx)):
        que.append([sy[i],sx[i]])
    
    while que:
        y,x = que.popleft()
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if 0<=nx and nx<w and 0<=ny and ny<h and d[ny][nx] == 10000000:
                if d[ny][nx] > d[y][x]+1:
                    d[ny][nx] = d[y][x]+1
                    que.append([ny,nx])
                    
                    if d[ny][nx] > ans:
                        ans = d[ny][nx]
    
    print(ans)
        
bfs()

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
H, W = map(int, input().split())
que = deque()
A = [input() for i in range(H)]

dist = [[-1]*W for i in range(H)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
for i in range(H):
  for j in range(W):
    if A[i][j] == '
      dist[i][j] = 0
      que.append((i, j))

d = 0
while que:
  y, x = que.popleft()
  d = dist[y][x]
  for dx, dy in dd:
    nx = x + dx; ny = y + dy
    if not 0 <= nx < W or not 0 <= ny < H or dist[ny][nx] != -1:
      continue
    dist[ny][nx] = d + 1
    que.append((ny, nx))

print(d)

Solution (Python):
H, W = map(int, input().split())
fields = [list(map(lambda c: c == '

checking = []
for i, row in enumerate(fields):
    for j, elem in enumerate(row):
        if elem:
            checking.append( (i, j) )

counter = 0
while True:
    to_check = []
    for y, x in checking:
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if 0 <= x+dx < W and 0 <= y+dy < H and not fields[y+dy][x+dx]:
                fields[y+dy][x+dx] = True
                to_check.append( (y+dy, x+dx) )

    if not to_check:
        break
    checking = to_check
    counter += 1

print(counter)

Solution (Python):
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    h,w = map(int,input().split())
    grid = [input() for _ in range(h)]
    q = deque([])
    dist = [[-1] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '
                dist[i][j] = 0
                q.append((i,j))
    
    ans = 0
    while q:
        i,j = q.popleft()
        for k in range(4):
            y = i + dy[k]
            x = j + dx[k]
            if y < 0 or y >= h:
                continue
            if x < 0 or x >= w:
                continue
            if dist[y][x] < 0:
                dist[y][x] = dist[i][j] + 1
                ans = max(ans,dist[y][x])
                q.append((y,x))
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
r, c = map(int, input().split())

cc = [input() for i in range(r)]

from collections import deque



st=[]
for i in range(r):
    for j in range(c):
        if cc[i][j]=="
            st.append([i,j])


todo=deque(st)

seen=[[-1 for i in range(c)] for j in range(r)]



for i in range(len(st)):
    seen[st[i][0]][st[i][1]]=0


ido=[[1,0],[0,1],[-1,0],[0,-1]]
m=0

while todo:
    y, x=todo.popleft() 
    for i in range(4): 
        ny, nx=y+ido[i][0], x+ido[i][1] 
        
        if 0<=ny<r and 0<=nx<c and seen[ny][nx]==-1 and cc[ny][nx]!="
            
            seen[ny][nx]=seen[y][x]+1 
            todo.append([ny,nx]) 
            if seen[ny][nx]>=m:
                m=seen[ny][nx]
       

print(m)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    A=[[] for _ in range(H+2)]
    A[0]=A[H+1]=['
    black=[]
    for i in range(1,H+1):
        row=list(input())
        A[i]=['
        for j,cell in enumerate(row):
            if cell=='
                black.append([i,j+1])
    nextcells=[]
    nextcells.extend(black)
    c=-1
    dx=[0,1,0,-1]
    dy=[1,0,-1,0]
    while nextcells:
        c+=1
        cells=[]
        cells.extend(nextcells)
        nextcells=[]
        for cell in cells:
            for k in range(4):
                if A[cell[0]+dy[k]][cell[1]+dx[k]]=='.':
                    nextcells.append([cell[0]+dy[k],cell[1]+dx[k]])
                    A[cell[0]+dy[k]][cell[1]+dx[k]]='
    print(c)
        

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def bfs(maze):
    h = len(maze)
    w = len(maze[0])
    visited = [[-1 for _ in range(w)] for _ in range(h)]
    d = deque()
    
    last =[-1, -1]
    for y in range(h):
        for x in range(w):
            if maze[y][x] == '
                d.append([y, x])
                visited[y][x] = 0
                last[0] = y
                last[1] = x
    
    while d:
        y, x = d.popleft()
        
        for l, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_y, new_x = y + l, x + k
            
            if new_y < 0 or h <= new_y or new_x < 0 or w <= new_x:
                continue
            elif visited[new_y][new_x] != -1:
                continue
            elif maze[new_y][new_x] == '
                continue
            
            d.append([new_y, new_x])
            visited[new_y][new_x] = visited[y][x] + 1

        last[0] = y
        last[1] = x
        
    ''' 確認用
    print(last)
    for i in range(h):
        print(visited[i])
    '''
        
    return visited[last[0]][last[1]]

if __name__ == "__main__":
    h, w = map(int, input().split())
    maze = []
    for i in range(h):
        maze.append(list(input()))
    ''' 確認用
    for i in range(h):
        print(maze[i])
    '''
    
    print(bfs(maze))

Solution (Python):
import sys
import collections

input = sys.stdin.readline

H, W = map(int, input().split())
q = collections.deque()
grid = []
for i in range(H):
    grid.append(list(input().strip()))
    for j in range(W):
        if grid[i][j] == "
            q.append((i, j, 0))

maxc = 0
while q:
    i, j, c = q.popleft()
    if maxc < c:
        maxc = c
    if i > 0 and grid[i - 1][j] == ".":
        q.append((i - 1, j, c + 1))
        grid[i - 1][j] = "
    if i < H - 1 and grid[i + 1][j] == ".":
        q.append((i + 1, j, c + 1))
        grid[i + 1][j] = "
    if j > 0 and grid[i][j - 1] == ".":
        q.append((i, j - 1, c + 1))
        grid[i][j - 1] = "
    if j < W - 1 and grid[i][j + 1] == ".":
        q.append((i, j + 1, c + 1))
        grid[i][j + 1] = "

print(maxc)

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

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
queue = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            dist[i][j] = 0
            queue.append((i, j))
while queue:
    i, j = queue.popleft()
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i+di, j+dj
        if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == -1:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
print(max(max(row) for row in dist))

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

H, W = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
dp = [[float('inf') if A[i][j] == '.' else 0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H):
    for j in range(W)[::-1]:
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
        if j < W-1:
            dp[i][j] = min(dp[i][j], dp[i][j+1] + 1)
for i in range(H)[::-1]:
    for j in range(W):
        if i < H-1:
            dp[i][j] = min(dp[i][j], dp[i+1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)
print(max(max(row) for row in dp))

Solution (Python):
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

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

    field = "
    field += "
    field += "

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            cost_now = cost[now]
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost_now + 1
                    enqueue(nv)
    
    starts = [i*(W+2)+j for j in range(1, W+1) for i in range(1, H+1) if field[i*(W+2)+j] == "
    dfs(starts)

    print(max(cost))

if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque
H,W = map(int,input().split())
A = [list(str(input())) for h in range(H)]

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


start = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == "
            start.append([h,w])
            C[h][w] = 0
            
while start:
    h,w = start.popleft()
    c_old = C[h][w]
    
    if h > 0:
        c_new = C[h-1][w]
        
        if c_new == -1:
            C[h-1][w] = c_old+1
            start.append([h-1,w])
            
    if w > 0:
        c_new = C[h][w-1]
        
        if c_new == -1:
            C[h][w-1] = c_old+1
            start.append([h,w-1])
            
    if w < W-1:
        c_new = C[h][w+1]
        
        if c_new == -1:
            C[h][w+1] = c_old+1
            start.append([h,w+1])
            
    if h < H-1:
        c_new = C[h+1][w]
        
        if c_new == -1:
            C[h+1][w] = c_old+1
            start.append([h+1,w])
            
            
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,C[h][w])
        
        
print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
que = deque()
A = [[0 for i in range(W)] for j in range(H)]
white_num = 0
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == '.':
            A[i][j] = -1
            white_num += 1
        elif S[j] == '
            A[i][j] = 0
            que.append([j, i])

ans = 0
while len(que) > 0:
    x, y = que.popleft()
    for k in range(4):
        nx = x + [1, 0, -1, 0][k]
        ny = y + [0, 1, 0, -1][k]
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if A[ny][nx] == -1:
            que.append([nx, ny])
            A[ny][nx] = A[y][x] + 1
            ans = max(ans, A[ny][nx])
print(ans)

Solution (Python):
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

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

    field = "
    field += "
    field += "

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost[now] + 1
                    enqueue(nv)
    
    starts = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            now = i*(W+2) + j
            if field[now] == "
                starts.append(now)
    dfs(starts)

    print(max(cost))

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

def bfs(q):
    tmp=deque(q)
    ch = [[False for i in range(W)] for j in range(H)]
    count = 0
    d=[[-1,0],[1,0],[0,-1],[0,1]]
    while tmp:
        x,y=tmp.popleft()
        for a,b in d:
            nx=x+a
            ny=y+b
            if 0<=nx<H and 0<=ny<W:
                if ch[nx][ny]!=True and A[nx][ny]==".":
                    V[nx][ny]=V[x][y]+1
                    ch[nx][ny]=True
                    tmp.append([nx,ny])
            else:
                continue
ju=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            ju.append([i,j])
bfs(ju)
for i in range(H):
    for j in range(W):
        if not A[i][j]=="
             ans=max(ans,V[i][j])
print(ans)

Solution (Python):
from collections import deque

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

def bfs(q):
    tmp=deque(q)
    ch = [[False for i in range(W)] for j in range(H)]
    count = 0
    d=[[-1,0],[1,0],[0,-1],[0,1]]
    while tmp:
        x,y=tmp.popleft()
        for a,b in d:
            nx=x+a
            ny=y+b
            if 0<=nx<H and 0<=ny<W:
                if ch[nx][ny]!=True and A[nx][ny]==".":
                    V[nx][ny]=V[x][y]+1
                    ch[nx][ny]=True
                    tmp.append([nx,ny])
            else:
                continue
ju=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            ju.append([i,j])
bfs(ju)
for i in range(H):
    for j in range(W):
        if not A[i][j]=="
             ans=max(ans,V[i][j])
print(ans)

Solution (Python):
from collections import deque

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

directions = [[-1,0],[1,0],[0,-1],[0,1]]

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

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

q = deque(B)

while q:
    nh,nw= q.pop()
    for dh,dw in directions:
        if not (0<= nh+dh < H and 0 <= nw+dw < W):
            continue
        elif D[nh+dh][nw+dw] != -1:
            continue
        elif A[nh+dh][nw+dw] == '
            D[nh+dh][nw+dw] = D[nh][nw]
            q.append([nh+dh,nw+dw])
        elif A[nh+dh][nw+dw] == '.':
            D[nh+dh][nw+dw] = D[nh][nw]+1
            q.appendleft([nh+dh,nw+dw])

print(max(max(D[i]) for i in range(H)))

Solution (Python):
from collections import deque

def bfs():
    global ans
    while q:
        p = q.popleft()
        for u in v:
            x, y = p[0] + u[0], p[1] + u[1]
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] == -1:
                    s[x][y] = s[p[0]][p[1]] + 1
                    q.append([x, y])
                    ans = max(ans, s[x][y])
    return

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
s = [[-1] * w for _ in range(h)]
v = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            s[i][j] = 0
            q.append([i, j])
bfs()
print(ans)

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

q=deque()
dist=[[-1]*(W+1) for a in range(H+1)]
G=[['
for i in range(1,H+1):
    G_comp=list(str(input()))
    for j in range(1,W+1):
        if G_comp[j-1]=='
            q.append((i,j))
            dist[i][j]=0
        G[i][j]=G_comp[j-1]

def sur(v):  
    vx=v[0]
    vy=v[1]
    preE=[(vx-1,vy),(vx+1,vy),(vx,vy-1),(vx,vy+1)]
    E=[]
    for nv in preE:
        if 1<=nv[0]<=H and 1<=nv[1]<=W:
            if G[nv[0]][nv[1]]=='.':
                E.append(nv)
    return E

while q:
    now=q.popleft()
    for next in sur(now):
        if dist[next[0]][next[1]]!=-1:
            continue
        q.append(next)
        dist[next[0]][next[1]]=dist[now[0]][now[1]]+1

M=[]
for k in range(1,H+1):
    M.append(max(dist[k]))

print(max(M))

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
inf = 10 ** 7

d = [[inf for _ in range(w)] for _ in range(h)]
que = deque()

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

while que:
    px, py = que.popleft()
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        qx, qy = px + dx, py + dy
        if 0 <= qx < h and 0 <= qy < w:
            if d[qx][qy] > d[px][py] + 1:
                d[qx][qy] = d[px][py] + 1
                que.append((qx, qy))

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

print(ans)

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
field = []
q = deque()
for i in range(H):
    line = []
    A = input()
    for j in range(W):
        if A[j] == ".":
            line.append(True)
        else:
            line.append(False)
            q.append(((j, i), 0))
    field.append(line)

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

ans = 0

while len(q) != 0:
    (x, y), d = q.popleft()
    ans = max(d, ans)
    for dir in dirs:
        nx = x + dir[0]
        ny = y + dir[1]
        if 0 <= nx <= W - 1 and 0 <= ny <= H - 1 and field[ny][nx]:
            field[ny][nx] = False
            q.append(((nx, ny), d+1))

print(ans)

Solution (Python):
from collections import deque
def mbfs(S,H,W,d):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    while(len(d)!=0):
        h=d[0][0]
        w=d[0][1]
        x=d[0][2]
        d.popleft()
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(S[nh][nw]=='
                continue
            S[nh][nw]='
            d.append([nh,nw,x+1])
    return x
H,W=map(int,input().split())
A=[list(input()) 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,0])
print(mbfs(A,H,W,d))

Solution (Python):
from collections import deque
def mbfs(S,H,W):
    dxy=[[1,0],[0,1],[-1,0],[0,-1]]
    while(len(d)!=0):
        h,w,x=d.popleft()
        for t,y in dxy:
            if(0<=h+t<=H-1 and 0<=w+y<=W-1 and S[h+t][w+y]!='
                S[h+t][w+y]='
                d.append([h+t,w+y,x+1])
    return x
H,W=map(int,input().split())
A=[list(input()) 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,0])
print(mbfs(A,H,W))

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

from collections import deque
fifo = deque()
a.append(["@"]*(w+2))
for i in range(h):
    s=input()
    temp=["@"]
    for j in range(w):
        if s[j]=="
            fifo.append([i+1,j+1])
            temp.append(0)
        else:
            temp.append(s[j])
    temp.append("@")
    a.append(temp)
a.append(["@"]*(w+2))

result=0


while len(fifo)>0:
    temp=fifo.popleft()
    y,x=temp[0],temp[1]

    for item in [[0,1],[1,0],[-1,0],[0,-1]]:
        
        if a[y+item[0]][x+item[1]]==".":
            fifo.append([y+item[0],x+item[1]])
            a[y+item[0]][x+item[1]]=a[y][x]+1
            result=max(result,a[y+item[0]][x+item[1]])
    
print(result)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '
            todo.append((x, y))
            seen[y][x] = True

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = -1
while todo:
    cnt += 1
    for _ in range(len(todo)):
        x, y = todo.popleft()
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))

print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '
            todo.append((x, y))
            seen[y][x] = True



dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = -1
while todo:
    cnt += 1
    for _ in range(len(todo)):
        x, y = todo.popleft()
        
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))








print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
todo = deque()
seen = [[False] * W for _ in range(H)]
route= [[0] * W for _ in range(H)]
for y in range(H):
    for x in range(W):
        if A[y][x] == '
            todo.append((x, y))
            seen[y][x] = True



dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
cnt = 0
while todo:
    for _ in range(len(todo)):
        x, y = todo.popleft()
        
        for i in range(4):
            if 0 <= x + dx[i] < W and 0 <= y + dy[i] < H:
                if seen[y + dy[i]][x + dx[i]] == False:
                    route[y + dy[i]][x + dx[i]] = route[y][x] + 1
                    seen[y + dy[i]][x + dx[i]] = True
                    todo.append((x + dx[i], y + dy[i]))
    



M = 0
for y in range(H):
    for x in range(W):
        M = max(M, route[y][x])
print(M)

Solution (Python):
from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0


for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "
            matrix_list1.append([i,j])


while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Solution (Python):
import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="
      q.append((i,j))

x=0
y=maze[:]

for i in q:
  maze[i[0]][i[1]]=0
while(q):
  c=q.popleft()
  for j in range(4):
    if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
      if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
        q.append((c[0]+dy[j],c[1]+dx[j]))
        maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
        
        x=max(x,maze[c[0]+dy[j]][c[1]+dx[j]])
print(x)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
memo = [[-1 if j=="." else 0 for j in list(i)] for i in a]

q = []
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            q.append([i, j])
q = deque(q)
while q:
    x, y = q.popleft()
    for s, t in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=x+s and 0<=y+t and x+s<h and y+t<w:
            if memo[x+s][y+t]<0:
                memo[x+s][y+t]=memo[x][y]+1
                q.append([x+s,y+t])
print(max(max(i) for i in memo))

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w = inm()
a = []
for i in range(h):
    a.append(list(ins()))
q = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='
            q.append((i,j))
cnt = 0


while len(q)>0:
    qq = []
    while len(q)>0:
        i,j = q.pop()
        for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            x = i+dx
            y = j+dy
            if 0<=x<h and 0<=y<w and a[x][y]=='.':
                a[x][y] = '
                qq.append((x,y))
    q = qq
    if len(q)>0:
        cnt += 1
    
    
print(cnt)

Solution (Python):






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

masu = [input() for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

distance = [[-1 for _ in range(w)] for _ in range(h)]

from collections import deque

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

ans = 0
while True:
    if len(queue) == 0:
        break
    now = queue.popleft()
    now_h = now[0]
    now_w = now[1]
    now_distance = distance[now_h][now_w]
    

    for i in range(4):
        next_h = now_h + dx[i]
        next_w = now_w + dy[i]
        if not (0 <= next_h <= h-1 and 0 <= next_w <= w-1):
            continue
        if distance[next_h][next_w] == -1:
            distance[next_h][next_w] = now_distance + 1
            queue.append((next_h, next_w))
            ans = now_distance + 1
            

print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
visited=[[-1]*w for _ in range(h)]
queue=deque()
for i in range(h):
  for j in range(w):
    if a[i][j]=='
      visited[i][j]=0
      queue.append([i,j])
while queue:
  y,x=queue.popleft()
  for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
    n_y,n_x=y+j,x+k
    if 0<=n_y<h and 0<=n_x<w and a[n_y][n_x]=='.' and visited[n_y][n_x]<0:
      visited[n_y][n_x]=visited[y][x]+1
      queue.append([n_y,n_x])
ans=0
for l in visited:
  ans=max([ans]+l)
print(ans)

Solution (Python):
from collections import deque

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.append((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


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

A = [[] for i in range(h)]
q = deque()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "
            d[i][j] = 0
            q.append((i, j, d[i][j]))

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

while len(q) > 0:
    idx = q.popleft()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)

Solution (Python):
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)