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



def bfs(maze, visited, queue, H, W):
    count = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + i, x + j
            if -1 < new_y < H and -1 < new_x < W:
                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])

    ans = -1
    for i in range(H):
        for j in range(W):
            ans = max(ans,visited[i][j])
    return ans

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

maze = [input() for i in range(H)]
visited = [[-1] * W for i in range(H)]

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

print(bfs(maze, visited, queue, H, W))

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):
import numpy as np

H, W = map(int, input().split())
max_value = H + W 
matrix = []


for _ in range(H):
    matrix.append([0 if i == '
matrix = np.array(matrix)

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

for c in range(W-1,0,-1):
    matrix[:,c-1] = np.minimum(matrix[:,c]+1, matrix[:,c-1]) 

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

for c in range(H-1,0,-1):
    matrix[c-1,:] = np.minimum(matrix[c,:]+1, matrix[c-1,:]) 

print (np.max(matrix))

Solution (Python):
from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
xy = [(0, 1), (0, -1), (1, 0), (-1, 0)]



def A():
    h, w = LI()
    A = SR(h)
    check = [[True for _ in range(w)] for i in range(h)]
    q = deque([])
    for tate in range(h):
        for yoko in range(w):
            if A[tate][yoko] == "
                q.append((tate, yoko))
                check[tate][yoko] = False
    new_q = deque([])
    ans = 0
    while True:
        while q:
            y, x = q.pop()
            for movex, movey in xy:
                if 0 <= y + movey < h and 0 <= x + movex < w and check[y + movey][x + movex]:
                    check[y + movey][x + movex] = False
                    new_q.append((y + movey, x + movex))
        if not new_q:
            break
        ans += 1
        q = new_q
        new_q = deque([])
    print(ans)
                    

        
    return


def B():
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    A()

Solution (Python):
from collections import deque
inf = float('inf')
around = [[0,1],[1,0],[0,-1],[-1,0]]

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

dq = deque()

for i,line in enumerate(A):
    for j,e in enumerate(line):
        if e == "
            dq.append([i,j,0])

def bfs():
    res = 0
    while dq:
        i,j,d = dq.popleft()
        d += 1
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if A[ni][nj] == ".":
                A[ni][nj] = "
                dq.append([ni,nj,d])
                if d > res:
                    res = d
    return res

ans = bfs()
print(ans)

Solution (Python):
h, w = map(int, input().split())
a = [['
a[1: 1] = (['
d = (-1, 0), (1, 0), (0, -1), (0, 1)

step = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1)
       if a[i][j] == '

def next_step():
    r = []
    for i, j in step:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '
                r.append((di, dj))
    return r

n = h * w - len(step)
r = 0
while n:
    r += 1
    step = next_step()
    n -= len(step)
print(r)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "
            mat.append((h, w, 0))
            s[w] = 1
        else:
            s[w] = 0
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == 0:
            mat.append((h, w, cnt+1))
            dp[h][w] = 1

print(cnt)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque(maxlen=W*H)
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "

print(cnt)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in [(h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)]:
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "

print(cnt)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "
            mat.append((h, w, 0))
    dp[h] = s

while len(mat):
    h, w, cnt = mat.popleft()

    for t, h, w, cnt in ((h > 0, h - 1, w, cnt),(h < H-1, h + 1, w, cnt),(w > 0, h , w - 1, cnt),(w < W-1, h , w + 1, cnt)):
        if t and dp[h][w] == ".":
            mat.append((h, w, cnt+1))
            dp[h][w] = "

print(cnt)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = deque()
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "
            mat.append((h, w, 0))
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    if dp[nH][nW] == ".":
        mat.append((nH, nW, cnt+1))
        dp[nH][nW] = "

while len(mat):
    h, w, cnt = mat.popleft()

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)

Solution (Python):
from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)

Solution (Python):
h, w = map(int, input().split())
a_array = [input() for x in range(h)]
black = [[False for x in range(w)] for y in range(h)]
next = set()
for row in range(h):
    for column in range(w):
        if a_array[row][column] == "
            black[row][column] = True
            next.add((row, column))

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = 0
while next:
    tmp = set()
    
    cnt += 1
    for row, column in next:
        for i, j in move:
            if not (0 <= row + i < h and 0 <= column + j < w) or black[row+i][column+j]:
                continue
            black[row+i][column+j] = True
            tmp.add((row + i, column + j))
    next = tmp
print(cnt-1)

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

step = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '

def next_step():
    r = []
    for i, j in step:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                r.append((di, dj))
    return r

n = h * w - len(step)
r = 0
while n:
    r += 1
    step = next_step()
    n -= len(step)
print(r)

Solution (Python):
def a_darker_and_darker(H, W, Grid):
    def is_in_field(row, col):
        return (0 <= row < H) and (0 <= col < W)

    grid, q = [[None] * W for _ in range(H)], []
    
    for row in range(H):
        for col in range(W):
            if Grid[row][col] == '
                grid[row][col] = True
                q.append((row, col))
            else:
                grid[row][col] = False

    
    
    directions = ((-1, 0), (0, 1), (1, 0), (0, -1))  
    ans = 0
    while q:
        tmp = []
        for row, col in q:
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if is_in_field(nr, nc) and (not grid[nr][nc]):
                    grid[nr][nc] = True
                    tmp.append((nr, nc))
        ans += (1 if tmp else 0)
        q = tmp
    return ans

H, W = [int(i) for i in input().split()]
Grid = [input() for _ in range(H)]
print(a_darker_and_darker(H, W, Grid))

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

from collections import deque
b=[[0]*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))
            b[i][j]=1
ans=-1
while len(q)>0:
    ans+=1
    q2=deque()
    for i,j in q:
        if j>0 and b[i][j-1]==0:
            q2.append((i,j-1))
            b[i][j-1]=1
        if j<w-1 and b[i][j+1]==0:
            q2.append((i,j+1))
            b[i][j+1]=1
        if i>0 and b[i-1][j]==0:
            q2.append((i-1,j))
            b[i-1][j]=1
        if i<h-1 and b[i+1][j]==0:
            q2.append((i+1,j))
            b[i+1][j]=1
    q=q2
print(ans)

Solution (Python):
from collections import deque

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

def bfs():
    queue = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j] == "
                queue.append([i, j])
                cnt[i][j] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                queue.append([i + di, j + dj])
                cnt[i + di][j + dj] = cnt[i][j] + 1

bfs()
print(max([max(l) for l in cnt]))

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '

def f():
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                s.append((di, dj))
    return s

n = h * w - len(p)
r = 0
while n:
    r += 1
    p = f()
    n -= len(p)
print(r)

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '
n = h * w - len(p)
r = 0
while n:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                s.append((di, dj))
    p = s
    n -= len(p)
print(r)

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '

def f():
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                yield di, dj

n = h * w - len(p)
r = 0
while n:
    r += 1
    p = list(f())
    n -= len(p)
print(r)

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '

def f():
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                yield di, dj

n = h * w - len(p)
r = 0
while n:
    r += 1
    p = list(f())
    n -= len(p)
print(r)

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '
n = h * w - len(p)
r = 0
while n:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                s.append((di, dj))
    p = s
    n -= len(p)
print(r)

Solution (Python):
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

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


bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1


print(max([max(l) for l in bfs]))

Solution (Python):
from scipy import ndimage
import numpy as np
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "

 

b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Solution (Python):
class Queue():
    def __init__(self):
        self.data = []
        self.idx = 0
        self.size = 0

    def get(self):
        self.idx += 1
        self.size -= 1
        return self.data[self.idx-1]

    def put(self, item):
        self.size += 1
        self.data.append(item)

    def qsize(self):
        return self.size

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


bfs = [[-1 for j in range(W)] for i in range(H)]
que = Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '
            que.put((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while(que.qsize()):
    p = que.get()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1


print(max([max(l) for l in bfs]))

Solution (Python):
from collections import deque


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


bfs = [[-1 for j in range(W)] for i in range(H)]
que = deque()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '
            que.append((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(len(que)):
    p = que.popleft()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.append((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1


print(max([max(l) for l in bfs]))

Solution (Python):
from scipy import ndimage
import numpy as np
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "

 
 

b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    
    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    
    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        
        
        
        
        
        
        
        
        
        
        
        

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    
    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
from scipy import ndimage
import numpy as np

 
H, W = map(int, input().split())
 
A_array = np.array(
    [[0 if s == "

 

b = ndimage.morphology.distance_transform_cdt(
    A_array, metric="taxicab")
print(np.max(b))

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

data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '
            que.append((ln, r))

count = 0

while len(que) > 0:
    count += 1
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in ((row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)):
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '
    que, next = next, que
    next.clear()

print(count - 1)

Solution (Python):
import numpy as np

H,W=map(int,input().split())
max_value = H+W
matrix =[]

for _ in range(H):
    matrix.append([0 if i == '
matrix = np.array(matrix)

for c in range(W-1):
    matrix[:,c+1] = np.minimum(matrix[:,c]+1,matrix[:,c+1])
for c in range(W-1,0,-1):
    matrix[:,c-1] = np.minimum(matrix[:,c-1],matrix[:,c]+1)
for r in range(H-1):
    matrix[r+1,:] = np.minimum(matrix[r,:]+1,matrix[r+1,:])
for r in range(H-1,0,-1):
    matrix[r-1,:] = np.minimum(matrix[r,:]+1,matrix[r-1,:])


print(np.max(matrix))

Solution (Python):
import collections
H,W=map(int,input().split())
went=[[False]*W for i in range(H)]
queue=collections.deque()
for hoge in range(H):
    for huga,t in enumerate(input()):
        if t=="
            went[hoge][huga]=True
            queue.append([hoge,huga,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)

Solution (Python):

import sys
from pprint import pprint
 
def solve(H: int, W: int, A: "List[str]"):
    count = [[H + W] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                count[i + 1][j + 1] = 0
            else:
                count[i + 1][j + 1] = min(count[i][j + 1], count[i + 1][j]) + 1
 
    
    ret = 0
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            count[i][j] = min(count[i][j], min(count[i][j + 1], count[i + 1][j]) + 1)
            ret = max(ret, count[i][j])
    
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    A = [next(tokens) for _ in range(H) ]  
    solve(H, W, A)
 
if __name__ == '__main__':
    main()

Solution (Python):

import sys
from pprint import pprint

def solve(H: int, W: int, A: "List[str]"):
    used = [[False] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, -1, 0, 1]
    s = set()
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                s.add((i, j))
                used[i][j] = True

    ret = 0
    while True:
        nex = set()
        for x, y in s:
            for j in range(4):
                tx = x + dx[j]
                ty = y + dy[j]
                if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
                    nex.add((tx, ty))
                    used[tx][ty] = True
        if len(nex) < 1:
            break
        s = nex
        ret += 1

    print(ret)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):

h, w = [int(i) for i in input().split()]
ary = []
for y in range(h):
    ary.append([None if i == '.' else 0 for i in input()])


from collections import deque

update_q = deque((y, x) for y, line in enumerate(ary) for x, elem in enumerate(line) if elem == 0)

def update(ary, update_q):
    for _ in range(len(update_q)):
        pos = update_q.popleft()
        y, x = pos
        if x > 0:
            uy, ux = y, x-1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if x < w-1:
            uy, ux = y, x+1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y > 0:
            uy, ux = y-1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y < h-1:
            uy, ux = y+1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
    return ary, update_q


black_count = len(update_q)
update_count = 0
while black_count < w * h:
    ary, update_q = update(ary, update_q)
    black_count += len(update_q)
    update_count += 1


print(update_count)

Solution (Python):
import numpy as np

H,W=map(int,input().split())
max_value = H+W
matrix =[]

for _ in range(H):
    matrix.append([0 if i == '
matrix = np.array(matrix)

for c in range(W-1):
    matrix[:,c+1] = np.minimum(matrix[:,c]+1,matrix[:,c+1])
for c in range(W-1,0,-1):
    matrix[:,c-1] = np.minimum(matrix[:,c-1],matrix[:,c]+1)
for r in range(H-1):
    matrix[r+1,:] = np.minimum(matrix[r,:]+1,matrix[r+1,:])
for r in range(H-1,0,-1):
    matrix[r-1,:] = np.minimum(matrix[r,:]+1,matrix[r-1,:])
print(np.max(matrix))

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '
                s.append((di, dj))
    p = s
print(r)

Solution (Python):

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from collections import deque



mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]


start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '
            start.append((i, j))
            visited[i][j] = True

n_white = W * H

que = deque([(si, sj, 0) for si, sj in start])

while que:
    y, x, cost = que.popleft()
    
    n_white -= 1
    if n_white == 0:
        print(cost)
        exit()

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True

Solution (Python):
h, w = map(int, input().split())
a = [['
a[1: 1] = [list('
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '
                s.append((di, dj))
    p = s
print(r)