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

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

c = [[10**9 for _ in range(W)] for _ in range(H)]
que = deque()

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

dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]      
      
while len(que) != 0:
  p = que.popleft()
  for i in dxy:
    nx = p[0] + i[0]
    ny = p[1] + i[1]
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] == 10**9 and maze[nx][ny] ==".":
      maze[nx][ny] = "
      c[nx][ny] = c[p[0]][p[1]] + 1
      que.append([nx, ny])
max = 0
for i in range(H):
  for j in range(W):
    if max < c[i][j]:
      max = c[i][j]
print(max)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from copy import *

H, W = map(int, input().split())
A = [input() for i in range(H)]
q = deque()
c = [[-1] * W for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            q.append((i, j))
            c[i][j] = 0
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while q:
    y, x = q.popleft()
    for dy, dx in D:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and c[ny][nx] == -1:
            q.append((ny, nx))
            c[ny][nx] = c[y][x]+1
print(max([max(l) for l in c]))

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        1 1 1    2 1 2
        1 0 1 -> 1 0 1
        1 1 1    2 1 2
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(input()) for _ in range(h))
    B = tuple(tuple(1 if i == "." else 0 for i in a) for a in A)
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        1 1 1    2 1 2
        1 0 1 -> 1 0 1
        1 1 1    2 1 2
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(input()) for _ in range(h))
    B = tuple(tuple(1 if i == "." else 0 for i in a) for a in A)
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        1 1 1    2 1 2
        1 0 1 -> 1 0 1
        1 1 1    2 1 2
    """
    _, _, *A = open(0).read().split()
    B = tuple(tuple(1 if i == "." else 0 for i in a) for a in A)
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        1 1 1    2 1 2
        1 0 1 -> 1 0 1
        1 1 1    2 1 2
    """
    _, _, *A = open(0).read().split()
    B = tuple(tuple(1 if i == "." else 0 for i in a) for a in A)
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Solution (Python):


from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        0 0 0    1 1 1
        0 1 0 -> 1 0 1
        0 0 0    1 1 1
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = list(list(input()) for _ in range(h))
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Solution (Python):

from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        0 0 0    1 1 1
        0 1 0 -> 1 0 1
        0 0 0    1 1 1
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = list(list(input()) for _ in range(h))
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

Solution (Python):
h, w = map(int, input().split())
a=[]
for i in range(h):
  a.append([it == '
q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]: q.append((i, j))
cnt = -1
while q:
  cnt += 1
  r = []
  for i, j in q:
    if i > 0 and not a[i-1][j]:
      a[i-1][j]=True
      r += [(i-1, j)]
    if i < h-1 and not a[i+1][j]:
      a[i+1][j]=True
      r += [(i+1, j)]
    ai = a[i]
    if j > 0 and not ai[j-1]:
      ai[j-1]=True
      r += [(i, j-1)]
    if j < w-1 and not ai[j+1]:
      ai[j+1]=True
      r += [(i, j+1)]
  q=r
print(cnt)

Solution (Python):
from collections import deque
from sys import stdin

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

N, M = [int(_) for _ in stdin.readline().rstrip().split()]
graph = []

def bfs(graph, N, M):
    for _ in range(N):
        n = list(stdin.readline().rstrip())
        graph.append(n)

    ans = 0
    que = deque()
    dist = [[-1 for i in range(M)] for j in range(N)]
    for i in range(N):
        for j in range(M):
            if graph[i][j] == '
                que.append((i, j)) 
                dist[i][j] = 0

    while len(que):
        v = que.popleft()
        for d in range(4):
            nx = v[0] + dx[d]
            ny = v[1] + dy[d]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[v[0]][v[1]] + 1
                que.append((nx, ny))

    for i in range(N):
        for j in range(M):
            ans = max(ans, dist[i][j])

    return ans

ans = bfs(graph, N, M)
print(ans)

Solution (Python):
from scipy.ndimage import distance_transform_cdt


h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
n = [[1 if x == '.' else 0 for x in row] for row in a]
cnt = distance_transform_cdt(n, metric='taxicab')
print(cnt.max())

Solution (Python):
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[99999]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "
      dist[i][j] = 0
      Q.append((i,j))

while Q:
  y,x = Q.popleft()
  for k in range(4):
    ny = y + Y[k]
    nx = x + X[k]
    if (0 <= nx < W) and (0 <= ny < H) and (C[ny][nx] == ".") and (dist[ny][nx] > dist[y][x]+1):
      Q.append((ny,nx))
      dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
Q = deque()
dist = [[99999]*W for i in range(H)]
for i in range(H):
  for j in range(W):
    if C[i][j] == "
      dist[i][j] = 0
      Q.append((i,j))

while Q:
  y,x = Q.popleft()
  for k in range(4):
    ny = y + Y[k]
    nx = x + X[k]
    if not (0 <= nx < W):
      continue
    if not (0 <= ny < H):
      continue
    if not (C[ny][nx] == "."):
      continue
    if not (dist[ny][nx] > dist[y][x]+1):
      continue
    Q.append((ny,nx))
    dist[ny][nx] = dist[y][x] + 1
ans = 0
for i in range(H):
  ans = max(ans,max(dist[i]))
print(ans)

Solution (Python):
from collections import deque
def bfs(maze, visited, l,n_w):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if n_w==0:
            s=set()
            tmp=0
            for i in visited:
                if max(i)>tmp:tmp=max(i)
            return(tmp)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                n_w-=1

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="
            l_b.append([i,j])
n_w=R*C-len(l_b)

print(bfs(maze, visited,l_b,n_w))

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [input() for _ in range(H)]
q = deque([])
grid = [[-1] * W for _ in range(H)]
dire = ((1,0),(0,1),(-1,0),(0,-1))
d = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            q.append((i,j))
            grid[i][j] = 0
 
while q:
    i, j = q.popleft()
    d = grid[i][j]
    for dy, dx in dire:
        ny,nx = i+dy, j+dx
        if ny>=0 and ny<H and nx>=0 and nx<W and grid[ny][nx] < 0:
            q.append((ny, nx))
            grid[ny][nx] = grid[i][j] + 1
 
print(d)

Solution (Python):
from collections import deque


H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]   
seen = [[False] * W for _ in range(H)] 
queue = deque([])

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

while queue:
    i,j,k=queue.popleft()
    if i!=0   and seen[i-1][j] == False: 
        queue.append((i-1,j,k+1))
        seen[i-1][j]=True
    if i!=H-1 and seen[i+1][j] == False:
        queue.append((i+1,j,k+1))
        seen[i+1][j]=True
    if j!=0   and seen[i][j-1] == False:
        queue.append((i,j-1,k+1))
        seen[i][j-1]=True
    if j!=W-1 and seen[i][j+1] == False:
        queue.append((i,j+1,k+1))
        seen[i][j+1]=True

print(k)

Solution (Python):
import numpy as np
import sys



buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
black = np.zeros((R+2,C+2),dtype=np.bool)
black[1:-1,1:] = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'

INF = 10 ** 9
dist = np.zeros((R,C),dtype=np.int32)
dist[~black[1:-1,1:-1]] = INF

for n in range(1,R):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(R-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,C):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(C-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)

Solution (Python):
import numpy as np
h,w = [int(i) for i in input().split()]
maximum = h+w
value = []
for i in range(h):
  value.append([0 if i == "
values = np.array(value)
for x in range(w-1):
  values[:,x+1] = np.minimum(values[:,x]+1,values[:,x+1])
for x in range(w-1,0,-1):
  values[:,x-1] = np.minimum(values[:,x]+1,values[:,x-1])
for y in range(h-1):
  values[y+1,:] = np.minimum(values[y,:]+1,values[y+1,:])
for y in range(h-1,0,-1):
  values[y-1,:] = np.minimum(values[y,:]+1,values[y-1,:])
print(values.max())

Solution (Python):
import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([0 if s == "

A = np.array(A)
for x in range(W - 1):
	A[:,x+1] = np.minimum(A[:, x]+1,A[:, x+1])
for x in range(W - 1, 0 , -1):
	A[:,x-1] = np.minimum(A[:, x-1],A[:, x]+1)
for y in range(H -1):
	A[y+1,:] = np.minimum(A[y, :]+1,A[y+1, :])
for y in range(H -1, 0, -1):
	A[y-1,:] = np.minimum(A[y-1, :],A[y, :]+1)

print(np.max(A))

Solution (Python):
INF = 10**9
H, W = map(int, input().split())
A = [list(input()) for h in range(H)]

ans = [[INF for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == '
            ans[h][w] = 0
        tmp = ans[h][w]+1
        if h < H-1:
            ans[h+1][w] = min(tmp, ans[h+1][w])
        if w < W-1:
            ans[h][w+1] = min(tmp, ans[h][w+1])
for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        tmp = ans[h][w]+1
        if h > 0:
            ans[h-1][w] = min(tmp, ans[h-1][w])
        if w > 0:
            ans[h][w-1] = min(tmp, ans[h][w-1])

print(max([w for h in ans for w in h]))

Solution (Python):
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
B = [list(stdin.readline().rstrip()) for _ in range(H)]

q = deque([])

for k in range(H):
    for l in range(W):
        if B[k][l] == '
            q.append((k, l, 0))

while len(q) > 0:
    h, w, t = q.popleft()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '
            q.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '
            q.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '
            q.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '
            q.append((h, w + 1, t + 1))
    if len(q) == 0:
        print(t)

Solution (Python):


import queue as que

from collections import deque 

def main():
    h, w = map(int, input().split())

    ahw = [input() for _ in range(h)]

    board = [[0]*w for _ in range(h)]

    q = deque()
    q.append((-1,-1))

    
    for hi in range(h):
        for wi in range(w):
            if ahw[hi][wi] == '

                board[hi][wi] = 1
                
                q.append((hi,wi) )



    if len(q) == h*w+1:
        print(0)
        return 
    

    def exec(h_,w_):
        if board[h_][w_] == 0:
            q.append((h_,w_))
            board[h_][w_] = 1
   
           
    ans = 0
    while q:
        t = q.popleft()

        th = t[0]; tw = t[1]

        if th == tw and tw == -1:
            if not q:
                break

            q.append((-1,-1))
            ans += 1
            continue

        if 0<th:
            exec(th-1, tw)
        if th+1 <h:
            exec(th+1, tw)
        if 0<tw:
            exec(th, tw-1)
        if tw +1 <w:
            exec(th, tw+1)

    print(ans-1)

main()

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

x = []

for _ in range(H):
    row = list( input() )
    x.append(row)

blacks = []
count = 0

for i in range(H):
    for j in range(W):
        a = x[i][j]
        if a == '
            count += 1
            blacks.append((i,j))

result = 0
DIRS = [(0,1),(0,-1),(1,0),(-1,0)]

while count < H*W:
    result += 1
    new_blacks = []
    for black in blacks:
        for dir in DIRS:
            i = black[0]+dir[0]
            j = black[1]+dir[1]
            if i < 0 or i >= H:
                continue
            if j < 0 or j >= W:
                continue
            if x[i][j] == '.':
                new_blacks.append((i,j))
                x[i][j] = '
                count += 1
    blacks = new_blacks

print(result)

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

blacks = []
cnt = 0

for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a == '
            cnt += 1
            blacks.append((i,j))

res = 0

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

while cnt < H*W:
    res += 1
    new_blacks = []
    for black in blacks:
        for dir in DIRS:
            i = black[0]+dir[0]
            j = black[1]+dir[1]
            if i < 0 or i >= H:
                continue
            if j < 0 or j >= W:
                continue
            if A[i][j] == '.':
                new_blacks.append((i,j))
                A[i][j] = '
                cnt += 1
    blacks = new_blacks

print(res)

Solution (Python):
import numpy as np

h, w = map(int, input().split())
max_value = h + w
values = []

for i in range(h):
    values.append([0 if i == '
values = np.array(values)

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

for x in range(w - 1, 0 , -1):
    values[:, x-1] = np.minimum(values[:, x-1], values[:, x] + 1)

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

for x in range(h - 1, 0, -1):
    values[x-1, :] = np.minimum(values[x, :] + 1, values[x-1, :])


print(np.max(values))

Solution (Python):
import numpy as np
def main():
    h,w = map(int, input().split())
    mat = []
    for i in range(h):
        b = input()
        mat.append([0 if j=="
    arr = np.array(mat)

    for i in range(w-1):
        arr[:,i+1] = np.minimum(arr[:,i]+1,arr[:,i+1])
        

    for i in range(w-1,0,-1):
        arr[:,i-1] = np.minimum(arr[:,i]+1,arr[:,i-1])
        

    for i in range(h-1):
        arr[i+1,:] = np.minimum(arr[i,:]+1,arr[i+1,:])
        

    for i in range(h-1,0,-1):
        arr[i-1,:] = np.minimum(arr[i,:]+1, arr[i-1,:])
        
    print(np.max(arr))


if __name__ == '__main__' :
    main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = ['
for i in range(h+2):
    a[i] = list(a[i])

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque([])
for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '
            q.append((i, j, 0))

ans = 0
while q:
    i, j, c = q.popleft()
    for di, dj in d:
        if a[i+di][j+dj] == '.':
            a[i+di][j+dj] = '
            q.append((i+di, j+dj, c+1))
    ans = max(ans, c)

print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = ['
for i in range(h+2):
    a[i] = list(a[i])

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

q = deque(x)
ans = 0
while q:
    i, j, c = q.popleft()
    for di, dj in d:
        if a[i+di][j+dj] == '.':
            a[i+di][j+dj] = '
            q.append((i+di, j+dj, c+1))
    ans = max(ans, c)


print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
a = ['
for i in range(h+2):
    a[i] = list(a[i])

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

ans = 0
while x:
    y = []
    for i, j in x:
        for di, dj in d:
            if a[i+di][j+dj] == '.':
                a[i+di][j+dj] = '
                y.append((i+di, j+dj))
    x = y
    ans += 1
    
    
    

ans -= 1
print(ans)

Solution (Python):
import numpy as np
import sys


buf = sys.stdin.buffer
H,W = map(int,buf.readline().split())
black = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'

INF = 10 ** 9
dist = np.zeros((H,W),dtype=np.int32)
dist[~black[:,:-1]] = INF

for n in range(1,H):
    np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
    np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,W):
    np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
    np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)

Solution (Python):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict







INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)








H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

bCnt = 0
for x in range(W):
    for y in range(H):
        if A[y][x] == '
            BQ.append((x, y))
            bCnt += 1


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False



DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]

cnt = 0

while bCnt != H * W:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[Y][X] == '.':
                A[Y][X] = '
                newBQ.append((X, Y))
                bCnt += 1

    cnt += 1

    
    
    
    

    BQ = newBQ

print(cnt)

Solution (Python):
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
dc=0
b=[]
for i in range(h):
  t=[]
  s=input()
  for j in range(w):
    if s[j]=="
    else:t.append(0)
  b.append(t)
count=0
while dc!=0:
  ld=dc
  dc=0
  for i in range(ld):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==0:b[x[0]+1][x[1]]=1;d.append((x[0]+1,x[1]));dc+=1
    if 0<x[0]:
      if b[x[0]-1][x[1]]==0:b[x[0]-1][x[1]]=1;d.append((x[0]-1,x[1]));dc+=1
    if x[1]<w-1:
      if b[x[0]][x[1]+1]==0:b[x[0]][x[1]+1]=1;d.append((x[0],x[1]+1));dc+=1
    if 0<x[1]:
      if b[x[0]][x[1]-1]==0:b[x[0]][x[1]-1]=1;d.append((x[0],x[1]-1));dc+=1
  count+=1
print(count-1)

Solution (Python):
from collections import deque

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

d = [[h+w for j in range(w)] for i in range(h)]
que = deque()


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

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


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

        if (0<=nx<w) and (0<=ny<h) and (d[ny][nx]==h+w):
            que.append((ny, nx))
            d[ny][nx] = d[p[0]][p[1]] + 1

res = max(map(max, d))
print(res)

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

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


while len(que):
    py, px = que.popleft()
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    for i, j in zip(dy, dx):
        ny = py + i
        nx = px + j
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if A[ny][nx] == '
            continue
        if visited[ny][nx] >= 0:
            continue
        visited[ny][nx] = visited[py][px] + 1
        que.append([ny, nx])

cnt = 0
for i in range(H):
    cnt = max(cnt, max(visited[i]))

print(cnt)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
C = []
Q = deque()
dist = [[-1]*W for i in range(H)]

for i in range(H):
  s = list(input())
  yxidx = [(i,x) for x,v in enumerate(s) if v == "
  for (y, x) in yxidx:
    Q.append((y,x))
    dist[y][x] = 0
  C.append(s)
X = [1,0,-1,0]
Y = [0,-1,0,1]


while Q:
  y,x = Q.popleft()
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dist[ny][nx] == -1):
      dist[ny][nx] = dist[y][x] + 1
      Q.append((ny,nx))

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

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))

ans = 0
for i in dp:
  ans = max(ans,max(i))
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np
from scipy.ndimage import distance_transform_cdt

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

H, W = list(map(int, sys.stdin.readline().split()))
A = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)]) == '.'
ret = distance_transform_cdt(A, metric='taxicab')
print(ret.max())

Solution (Python):
import os

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

H, W = list(map(int, sys.stdin.readline().split()))
A = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W and A[h][w] == '.'


nexts = []
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == '
        nexts.append((h, w))

delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
ans = 0
while nexts:
    nn = []
    for dh, dw in delta:
        for h, w in nexts:
            if ok(h + dh, w + dw):
                A[h + dh][w + dw] = '
                nn.append((h + dh, w + dw))
    if not nn:
        break
    ans += 1
    nexts = nn
print(ans)

Solution (Python):
import sys
from collections import deque


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

visited = [[False]*w for i in range(h)]
q = deque([])
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            q.append((i, j, 0))
            visited[i][j] = True
ans = 0
while q:
    i, j, times = q.popleft()
    ans = max(times, ans)
    for next_i, next_j in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
        if 0 <= next_i < h and 0 <= next_j < w and not visited[next_i][next_j]:
            visited[next_i][next_j] = True
            q.append((next_i, next_j, times + 1))
print(ans)

Solution (Python):
from collections import deque

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

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

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

for h in range(H):
    for w in range(W):
        if src[h][w]=="
            dist[h][w]=0
            d.append((w,h))
while d:
    x,y = d.popleft()
    for dx, dy in dxy:
        nx,ny = x+dx, y+dy
        if not 0<=nx<W: continue
        if not 0<=ny<H: continue
        if src[ny][nx] == "
        if dist[ny][nx] > 0: continue
        dist[ny][nx] = dist[y][x] + 1
        d.append((nx,ny))
print(max(map(max,dist)))

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

M = [list(map(lambda x:0 if x == "

def set(i, j, x):
    if x < 0 or M[i][j] == 0:
        return
    x += 1
    if M[i][j] < 0:
        M[i][j] = x
    else:
        M[i][j] = min(M[i][j], x)

for i in range(H):
    for j in range(W):
        if j > 0:
            set(i, j, M[i][j-1])
        if i > 0:
            set(i, j, M[i-1][j])

for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        if j < W-1:
            set(i, j, M[i][j+1])
        if i < H-1:
            set(i, j, M[i+1][j])

print(max(y for x in M for y in x))

Solution (Python):
from collections import deque



def main():
    h,w=map(int,input().split())
    w+=2

    a=[list('@'*w)]
    for i in range(h):
        a+=[list('@'+input()+'@')]
    a+=[list('@'*w)]
    h+=2

    xy=[(-1,0),(0,-1),(0,1),(1,0)]
    que=deque()



    A=[[float('inf')]*w for i in range(h)]

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


    res=0
    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))
                res=max(res,tmp)

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

a=[list('@'*w)]
for i in range(h):
    a+=[list('@'+input()+'@')]
a+=[list('@'*w)]
h+=2

xy=[(-1,0),(0,-1),(0,1),(1,0)]
que=deque()

def bfs():
    res=0
    while que:
        x,y=que.popleft()
        for dx,dy in xy:
            nx,ny=dx+x,dy+y
            tmp=A[x][y]+1
            if a[nx][ny]!='@':
                if A[nx][ny]<=tmp:continue
                A[nx][ny]=tmp
                que.append((nx,ny))
                res=max(res,tmp)
    return res


A=[[float('inf')]*w for i in range(h)]

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

res=bfs()
print(res)