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



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

data = []

for _ in range(H):
    data.append(list(input()))

searched = [[0]*(W+2)]

for _ in range(H):
    searched.append([0] + [1000000]*W + [0])
searched.append([0]*(W+2))

visit_p = deque()
for h,i in enumerate(data):
    for w, j in enumerate(i):
        if j == "#":
            searched[h+1][w+1] = 0
            visit_p.append((h+1, w+1, 0))
while visit_p:
    nh,nw,num = visit_p.popleft()
    if searched[nh][nw] < num:
        continue
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        if searched[nh+dh][nw+dw] > num + 1:
            searched[nh+dh][nw+dw] = num + 1
            visit_p.append((nh+dh,nw+dw,num+1))
print(max(map(max, searched)))

Submission status: Accepted

Solution code:
# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_cdt.html
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()

Submission status: Accepted

Solution code:
# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_cdt.html
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()

Submission status: Accepted

Solution code:
# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_cdt.html
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()

Submission status: Accepted

Solution code:
# AGC033A - Darker and Darker
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()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from collections import deque


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

Submission status: Accepted

Solution code:
import numpy as np
import sys
# 距離K以内にxが居ない
# xからの距離を測る

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'#').reshape(R,C+1)

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)

Submission status: Accepted

Solution code:
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 == "#" else maximum for i in list(input())])
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())

Submission status: Accepted

Solution code:
import numpy as np

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

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

# 遅い…？
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))
#    q = [(-1,-1)]
    
    for hi in range(h):
        for wi in range(w):
            if ahw[hi][wi] == '#':

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

#    print(q)
#    print(board)
    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()
#        print(t)
        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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 == '#' else max_value for i in list(input())])
values = np.array(values)
#print(values)
for x in range(w - 1):
    values[:, x+1] = np.minimum(values[:, x] + 1, values[:, x+1])
#print(values)
for x in range(w - 1, 0 , -1):
    values[:, x-1] = np.minimum(values[:, x-1], values[:, x] + 1)
#print(values)
for x in range(h - 1):
    values[x+1, :] = np.minimum(values[x, :] + 1,values[x+1, :])
#print(values)
for x in range(h - 1, 0, -1):
    values[x-1, :] = np.minimum(values[x, :] + 1, values[x-1, :])
#print(values)

print(np.max(values))

Submission status: Accepted

Solution code:
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=="#" else h+w for j in b])
    arr = np.array(mat)

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

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

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

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


if __name__ == '__main__' :
    main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = ['#' * (w+2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w+2)]
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)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = ['#' * (w+2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w+2)]
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)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = ['#' * (w+2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w+2)]
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
    # for i in range(h+2):
    #     print("".join(a[i]))
    # print()

ans -= 1
print(ans)

Submission status: Accepted

Solution code:
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'#').reshape(H,W+1)

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)

Submission status: Accepted

Solution code:
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]=="#":d.append((i,j));dc+=1;t.append(1)
    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)

Submission status: Accepted

Solution code:
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()
    # 黒にする4方向をループ
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))
ans = 0
for i in dp:
  ans = max(ans,max(i))
print(ans)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['#'], dire=[(1,0), (0,1), (-1,0), (0,-1)], return_maximum_distance=False):
    H = len(c)
    W = len(c[0])
    distance_limit = H*W+1
    dist = [[distance_limit]*W for i in range(H)]

    q = deque()

    q_append = q.append
    q_popleft = q.popleft

    if (type(sy)==list) or (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q_append((sy, sx))

    while q:
        y, x = q_popleft()
        d = dist[y][x]
        for dy, dx in dire:
            if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                if (c[y+dy][x+dx] in blocks):
                    continue
                else:
                    if (y+dy==gy) and (x+dx==gx) and (not return_maximum_distance):
                        return (d+1)
                    elif (dist[y+dy][x+dx] > d+1):
                        dist[y+dy][x+dx] = d+1
                        q_append((y+dy, x+dx))
    if (return_maximum_distance):
        return d
    return -1

H, W = LI()
c = SR(H)

sy = []
sx = []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="#"):
            sy.append(i)
            sx.append(j)

print(bfs(c, sy, sx, return_maximum_distance=True))



def bfs(c,sy=0, sx=0, gy=0, gx=0, blocks=['#'], dire=[(1,0), (0,1), (-1,0), (0,-1)], return_maximum_distance=False):
            H = len(c)
            W = len(c[0])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def bfs(sy=0, sx=0, c=[['.']], gy=0, gx=0, blocks=['#'], return_maximum_distance=False):
    H = len(c)
    W = len(c[0])
    dire = [(1,0), (0,1), (-1,0), (0,-1)]
    dist = [[1000000007]*W for i in range(H)]

    q = deque()

    if (type(sy)==list) and (type(sx)==list):
        for syi, sxi in zip(sy, sx):
            dist[syi][sxi] = 0
            q.append((syi, sxi))
    else:
        dist[sy][sx] = 0
        q.append((sy, sx))

    if (return_maximum_distance):
        while q:
            y, x = q.popleft()
            for dy, dx in dire:
                if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                    if (c[y+dy][x+dx] in blocks):
                        continue
                    elif (dist[y+dy][x+dx] > dist[y][x]+1):
                            dist[y+dy][x+dx] = dist[y][x]+1
                            q.append((y+dy, x+dx))
        maximum_distance = 0
        for i in range(H):
            for j in range(W):
                if (dist[i][j] < 1000000007):
                    maximum_distance = max(dist[i][j], maximum_distance)
        return maximum_distance

    else:
        while q:
            y, x = q.popleft()
            for dy, dx in dire:
                if (y+dy<H) and (y+dy>=0) and (x+dx<W) and (x+dx>=0):
                    if (c[y+dy][x+dx] in blocks):
                        continue
                    else:
                        if (y+dy==gy) and (x+dx==gx):
                            return (dist[y][x]+1)
                        elif (dist[y+dy][x+dx] > dist[y][x]+1):
                            dist[y+dy][x+dx] = dist[y][x]+1
                            q.append((y+dy, x+dx))
        return -1

H, W = LI()
c = SR(H)

sy, sx = [], []

for i in range(H):
    for j in range(W):
        if (c[i][j]=="#"):
            sy.append(i)
            sx.append(j)

print(bfs(sy, sx, c, return_maximum_distance=True))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from collections import deque

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

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)

Submission status: Accepted

Solution code:
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'#').reshape(H,W+1)

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)

Submission status: Accepted

Solution code:
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 == '#' else max_value for i in list(input())])
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))

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
graph=[[0 if i=='#' else float('inf') for i in list(input())] for _ in range(h)]
graph=np.array(graph)
for x in range(w-1):
    graph[:,x+1]=np.minimum(graph[:,x]+1,graph[:,x+1])
for x in range(w-1,0,-1):
    graph[:,x-1]=np.minimum(graph[:,x]+1,graph[:,x-1])
for y in range(h-1):
    graph[y+1,:]=np.minimum(graph[y,:]+1,graph[y+1,:])
for y in range(h-1,0,-1):
    graph[y-1,:]=np.minimum(graph[y,:]+1,graph[y-1,:])

print(int(np.max(graph)))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def solve():
	H, W = MAP()
	A = [input() for _ in range(H)]

	count = [[0]*W for _ in range(H)]
	q = deque([])

	for i in range(H):
		for j in range(W):
			if A[i][j] == "#":
				q.append((i, j))
	# print(q)

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

	while len(q) >= 1:
		i, j = q.popleft()
		# print(i, j)
		for x, y in zip(dx, dy):
			ny = i + y
			nx = j + x
			if 0 <= nx <= W-1 and 0 <= ny <= H-1 and count[ny][nx] == 0 and A[ny][nx] != "#":
				count[ny][nx] = count[i][j] + 1
				q.append((ny, nx))

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

if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
import numpy as np


def solve():
    h, w = map(int, input().split(' '))
    max_value = h + w
    values = []
    for i in range(h):
        values.append([0 if i == '#' else max_value for i in list(input())])
    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))


solve()