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: Runtime Error

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]
display(a)

ans = 0
while True:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            ns.append((i-1, j))
        if a[i+1][j]:
            ns.append((i+1, j))
        if a[i][j-1]:
            ns.append((i, j-1))
        if a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    a.append([])
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

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

while s:
    q, s = s[0], s[1:]
    if a[q[0]][q[1]] != -1:
        continue
    
    a[q[0]][q[1]] = q[2]
    ans = q[2]
    
    if q[0]>0:
        s.append((q[0]-1, q[1], q[2]+1))
    if q[0]<h-1:
        s.append((q[0]+1, q[1], q[2]+1))
    if q[1]>0:
        s.append((q[0], q[1]-1, q[2]+1))
    if q[1]<w-1:
        s.append((q[0], q[1]+1, q[2]+1))
        
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int,input().split())
A = list(list(str(input())) for _ in range(H))
X = []

def count(A, value):
    return [i for i, x in enumerate(A) if x == value]

def black(X):
  for i in range(H):
    if len(count(A[i], '#')) != 0:
      for k in count(A[i], '#'):
        X.append([i, k])
  return X

def dist(i,j,X):
  Z = []
  for k in range(len(X)):
    Z.append(abs(i-X[k][0]) + abs(j-X[k][1]))
  z = min(Z)
  return z

Y = []
for i in range(H):
  for j in range(W):
    Y.append(dist(i,j,black(X)))
Y = [y for y in Y if y != 0]

if len(black(X)) == H*W:
  print(0)
else:
  print(max(Y))

Submission status: Runtime Error

Solution code:
H, W = map(int,input().split())
A = list(list(str(input())) for _ in range(H))
X = []

def count(A, value):
    return [i for i, x in enumerate(A) if x == value]

def black(X):
  for i in range(H):
    if len(count(A[i], '#')) != 0:
      for k in count(A[i], '#'):
        X.append([i, k])
  return X

def dist(i,j,X):
  Z = []
  for k in range(len(X)):
    Z.append(abs(i-X[k][0]) + abs(j-X[k][1]))
  z = min(Z)
  return z

Y = []
for i in range(H):
  for j in range(W):
    Y.append(dist(i,j,black(X)))
Y = [y for y in Y if y != 0]
print(max(Y))

Submission status: Runtime Error

Solution code:
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    for i in range(h):
        f.append(list(input()))
    #カウンター用のフィールド
    d = [[-1 for j in range(w)] for i in range(h)]
    q = deque()
    for i in range(h):
        for j in range(w):
            if f[i][j] == '#':
                # スタート地点のメモ
                d[i][j] = 0
                q.appendleft((i, j))

    while q:
        y, x = q.pop()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny, nx = y+dy, x+dx
            # 行ったことない場合に限る
            if 0 <= ny < h and  0 <= nx < w and d[ny][nx] == -1:
                d[ny][nx] = d[y][x] + 1
                q.appendleft((ny, nx))

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from heapq import heappush, heappop
    input = sys.stdin.readline
    H, W = map(int, input().split())
    D = [None]*H
    Q = []
    for h in range(H):
        D[h] = [10e10]*W
        l = input().strip()
        for w in range(W):
            if l[w] == "#":
                D[h][w] = 0
                Q.append((0, h, w))

    m = 0
    while Q:
        d, h, w = heappop(Q)
        alt = d+1
        m = max(m, d)
        for dx, dy in [(-1,0), (1,0), (0,-1), (0, +1)]:
            h1, w1 = h+dx, w+dy
            if 0 <= h1 < H and 0 <= w1 < W:
                if D[h1][w1] > alt:
                    D[h1][w1] = alt
                    heappush(Q, (alt, h1, w1))

    #for h in range(H): print(D[h])
    print(m)

main()

Submission status: Runtime Error

Solution code:
def bfs():
    q = queue.Queue()

    left = H * W
    newtarget = 0
    for h in range(H):
        for w in range(W):
            if Data[h][w] == '#':
                q.put([h,w])
                left -= 1
                newtarget +=1

    diff = [[1,0],[-1,0],[0,1],[0,-1]]

    count = 0
    while left > 0:
        count += 1
       
        target = newtarget
        newtarget = 0
        for _ in range(target):
            h,w = q.get()

            for di in diff:
                hh = h + di[0]
                ww = w + di[1]

                if hh >= 0 and ww >= 0 and hh < H and ww < W:
                    if Data[hh][ww] == '.':
                        Data[hh][ww] = '#'
                        left -= 1
                        newtarget += 1
                        q.put([hh,ww])
    return count


H,W = map(int,input().split())
for _ in range(H):
    Data.append(list(input()))
for r in range(H):
    Path.append([-1]*W)
ans = bfs()
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        new_stack = deque()
        for a,b in stack:
        #while stack:
            a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, a in enumerate(S):
        if a == "#":
            Q.append((y, x))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        y, x = Q.pop()
        if x > 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((y,x-1))
        if x < W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((y,x+1))
        if y > 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((y-1, x))
        if y < H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((y+1,x))
    if NQ:
        Q = NQ.copy()
    else:
        break

print(ans-1)

Submission status: Runtime Error

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

A = [[False for _ in range(W)] for _ in range(H)]

Q = deque()
for y in range(H):
    S = input()
    for x, a in enumerate(S):
        if a == "#":
            Q.append((x, y))
            A[y][x] = True

ans = 0
while True:
    ans += 1
    NQ = deque()
    while Q:
        x, y = Q.pop()
        if y != 0 and A[y-1][x] == False:
            A[y-1][x] = True
            NQ.append((x,y-1))
        if y != H-1 and A[y+1][x] == False:
            A[y+1][x] = True
            NQ.append((x,y+1))
        if x != 0 and A[y][x-1] == False:
            A[y][x-1] = True
            NQ.append((x-1,y))
        if x != W-1 and A[y][x+1] == False:
            A[y][x+1] = True
            NQ.append((x+1,y))
    if NQ:
        Q = NQ.copy()
    else:
        break

print(ans-1)

Submission status: Runtime Error

Solution code:
x=input().split()
a=int(x[0])
b=int(x[1])
x=[]
n=0
for i in range(a):
    y=[p for p in input()]
    x.append(y)
flag=True
while flag:
    s=[]
    ss=[]
    for i in range(a):
        for j in range(b):
            if x[i][j]=='#':
                ss.append(i)
                ss.append(j)
                s.append(ss)
                ss=[]
    for i in s:
        y=i[0]
        z=i[1]
        if y-1>=0:
            x[y-1][z]='#'
        if y+1<b:
            x[y+1][z]='#'
        if z-1>=0:
            x[y][z-1]='#'
        if z+1<b:
            x[y][z+1]='#'
    n+=1
    flag=False
    for i in range(a):
        for j in range(b):
            if x[i][j]=='.':
                flag=True
print(n)

Submission status: Runtime Error

Solution code:
from collections import deque


H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = deque()
A_append = A.append
q_append = q.append
for _ in range(H):
    a = input()
    A_append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

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 len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[1] + dy[k]
        x = p[0] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q_append([y, x, c + 1])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = deque()
for _ in range(H):
    a = input()
    A.append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

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

ans = 1

while len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[1] + dy[k]
        x = p[0] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q.append([y, x, c + 1])

print(ans - 1)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = deque()
for _ in range(H):
    a = input()
    A.append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

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

ans = 0

while len(q) != 0:
    p = q.popleft()
    for k in range(4):
        y = p[1] + dy[k]
        x = p[0] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q.append([y, x, c + 1])

print(ans - 1)

Submission status: Runtime Error

Solution code:
import copy
import queue

H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = queue.Queue()
for _ in range(H):
    a = input()
    A.append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            q.put([i, j, 1])

ans = 0

while not q.empty():
    p = q.get()
    for k in range(4):
        y = p[1] + dy[k]
        x = p[0] + dx[k]
        c = p[2]
        ans = max(ans, c)
        if A[y][x] == '.':
            A[y][x] = '#'
            q.put([y, x, c + 1])

print(ans - 1)

Submission status: Runtime Error

Solution code:
import copy
import queue

H, W = map(int, input().split())
A = [list('#' * (W + 2))]
q = queue.Queue()
for _ in range(H):
    a = input()
    A.append(list('#' + a + '#'))
A.append(list('#' * (W + 2)))
B = copy.deepcopy(A)
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            q.put([i, j])
q.put([])

ans = 0
count = 0
while not q.empty():
    count = 0
    p = q.get()
    if p == []:
        ans += 1
        A = copy.deepcopy(B)
        if not q.empty():
            q.put([])
    else:
        for k in range(4):
            y = p[1] + dy[k]
            x = p[0] + dx[k]
            if A[y][x] == '.':
                B[y][x] = '#'
                q.put([y, x])

print(ans - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
import itertools
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

start = []

for i in range(1,h-1):
    for j in range(1,w-1):
        if maze[i][j] == '#':
            start.append((i,j,0))

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

for t in range(len(start)):
    que = deque()
    que.append(start[t])
    
    while que:
        i,j,k = que.popleft() #先頭を取得
        for di,dj in move:
            if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
                distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
                que.append((i+di,j+dj,k+1)) #queの末尾に追加            

ans = itertools.chain(*distance)
ans = list(ans)
ans = [i for i in ans if i != float('inf')]

print(max(ans))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
  A.append(list(map(int,input().replace(".", "0").replace("#", "1"))))
V = []
v = []
c = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == 1:
      V.append([i, j])
for i in range(H+W):
  P = []
  if len(V) == H*W:
    break
  c += 1
  for v in V:
    if v not in P:
      P.append(v)
    if v[0]!=0 and [v[0]-1, v[1]] not in P:
      P.append([v[0]-1, v[1]])
    if v[1]!=0 and [v[0], v[1]-1] not in P:
      P.append([v[0], v[1]-1])
    if v[0]!=(H-1) and [v[0]+1, v[1]] not in P:
      P.append([v[0]+1, v[1]])
    if v[1]!=(W-1) and [v[0], v[1]+1] not in P:
      P.append([v[0], v[1]+1])
  V = P - V
print(c)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
  A.append(list(map(int,input().replace(".", "0").replace("#", "1"))))
V = []
v = []
c = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == 1:
      V.append([i, j])
for i in range(H+W):
  P = []
  if len(V) == H*W:
    break
  c += 1
  for v in V:
    if v not in P:
      P.append(v)
    if v[0]!=0 and [v[0]-1, v[1]] not in P:
      P.append([v[0]-1, v[1]])
    if v[1]!=0 and [v[0], v[1]-1] not in P:
      P.append([v[0], v[1]-1])
    if v[0]!=(H-1) and [v[0]+1, v[1]] not in P:
      P.append([v[0]+1, v[1]])
    if v[1]!=(W-1) and [v[0], v[1]+1] not in P:
      P.append([v[0], v[1]+1])
  #VをPではなくP¥Vに更新したい…
  V = P - V
print(c)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(h: int, w: int, a: "List[str]"):
    a = [[j == "#" for j in a[i]] for i in range(h)]
    que = collections.deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = collections.deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(H: int, W: int, A: "List[str]"):
    import sys
    import numpy as np
    from scipy.ndimage.morphology import distance_transform_cdt
    INPUT = lambda: sys.stdin.readline().rstrip()
    MAP = lambda: map(int, INPUT().split())
    sys.setrecursionlimit(10 ** 9)

    A = np.array([[(Ai[j] != "#") for j in range(W)] for Ai in A])
    print(distance_transform_cdt(A, metric="taxicab").max())

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[-1] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "#":
            cnt += 1
            reached[y][i] = 0
            tempList.append((i + 1, y, -1))
            tempList.append((i - 1, y, -1))
            tempList.append((i, y + 1, -1))
            tempList.append((i, y - 1, -1))

q.append(tempList)


def BFS(blist):
    global count
    global cnt
    tList = []

    count += 1

    for (x, y, pre) in blist:
        if x >= W or y >= H or x < 0 or y < 0 or reached[y][x]>=0:
            continue

        reached[y][x] = pre + 1
        Map[y][x] = "#"

        tList.append((x + 1, y, pre + 1))
        tList.append((x - 1, y, pre + 1))
        tList.append((x, y + 1, pre + 1))
        tList.append((x, y - 1, pre + 1))

    if np.where(np.array(reached)>=0, True, False).all():
        print(count)
        sys.exit()

    q.append(tList)


while q:
    BFS(q.popleft())

Submission status: Runtime Error

Solution code:
# from collections import deque
# import numpy as np
# import sys
#
# H, W = map(int, input().split())
#
# Map = [[] for _ in range(H)]
# reached = [[False]*W for _ in range(H)]
# q = deque()
# cnt = 0
# count = 0
# tempList = []
# for y in range(H):
#     for i, x in enumerate(input()):
#         Map[y].append(x)
#         if x=="#":
#             reached[y][i] = True
#             if i + 1 < W and not reached[y][i + 1]:
#                 tempList.append((i + 1, y))
#
#             if i - 1 >= 0 and not reached[y][i - 1]:
#                 tempList.append((i - 1, y))
#
#             if y + 1 < H and not reached[y + 1][i]:
#                 tempList.append((i, y + 1))
#
#             if y - 1 >= 0 and not reached[y - 1][i]:
#                 tempList.append((i, y - 1))
#
# q.append(tempList)
#
# def BFS(blist):
#     global count
#     tList = []
#
#     count += 1
#
#     for (x, y) in blist:
#         reached[y][x] = True
#         Map[y][x] = "#"
#         if x+1<W and not reached[y][x + 1]:
#             tList.append((x + 1, y))
#
#         if x-1>=0 and not reached[y][x - 1]:
#             tList.append((x - 1, y))
#
#         if y+1<H and not reached[y + 1][x]:
#             tList.append((x, y + 1))
#
#         if y-1>=0 and not reached[y - 1][x]:
#             tList.append((x, y - 1))
#
#     if np.array(reached).all():
#         print(count)
#         sys.exit()
#
#     q.append(tList)
#
# while q:
#     BFS(q.popleft())

from collections import deque
import numpy as np
import sys

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

Map = [[] for _ in range(H)]
reached = [[False] * W for _ in range(H)]
q = deque()
cnt = 0
count = 0
tempList = []
for y in range(H):
    for i, x in enumerate(input()):
        Map[y].append(x)
        if x == "#":
            cnt += 1
            reached[y][i] = True
            tempList.append((i + 1, y))
            tempList.append((i - 1, y))
            tempList.append((i, y + 1))
            tempList.append((i, y - 1))

q.append(tempList)


def BFS(blist):
    global count
    global cnt
    tList = []

    count += 1

    for (x, y) in blist:
        if x >= W or y >= H or x < 0 or y < 0 or reached[y][x]:
            continue

        reached[y][x] = True
        Map[y][x] = "#"
        cnt += 1

        tList.append((x + 1, y))
        tList.append((x - 1, y))
        tList.append((x, y + 1))
        tList.append((x, y - 1))

    if cnt == H * W:
        print(count)
        sys.exit()

    q.append(tList)


while q:
    BFS(q.popleft())

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


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

    A = np.array([[(Ai[j] != "#") for j in range(W)] for Ai in A])
    print(distance_transform_cdt(A, metric="taxicab").max())


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs():
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x] == '#':
        q.append((y, x))
        dist[y][x] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] < dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
bfs()
print(max([max[i] for i in dist]))

Submission status: Runtime Error

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

def clear(A):
    
    INF = 100000000

    distance = [[INF for i in range(W)] for j in range(H)]

    def bfs():
        queue = []
        already = []

        for i in range(W):
            for j in range(H):
                if A[i][j] == "#":
                    queue.insert(0,(i,j))
                    already.insert(0,(i,j))
                    distance[i][j] = 0

        while len(queue):
            x, y = queue.pop()

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < W and 0 <= ny and ny < H and \
                    A[nx][ny] == '.' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    already.insert(0, (nx,ny))
                    distance[nx][ny] = distance[x][y] + 1

        max_dis = 0
        for i in range(H):
            max_dis = max(max_dis,max(distance[i]))

        return max_dis

    return bfs()

print (clear(a_list))

Submission status: Runtime Error

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

from collections import deque

q=deque([])
B=[[None]*H for _ in range (W)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.append((i,j))
            B[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while len(q)>0:
  XY=[]
  while len(q)>0:
     XY.append(q.popleft())
  for xy in XY:
    for i in range(4):
      if 0<=(xy[0]+dx[i])<=H-1 and 0<=(xy[1]+dy[i])<=W-1:
        if B[xy[0]+dx[i]][xy[1]+dy[i]]==None:
          B[xy[0]+dx[i]][xy[1]+dy[i]]=B[xy[0]][xy[1]]+1
          q.append((xy[0]+dx[i],xy[1]+dy[i]))
        else: pass
      else: pass
print(max([max(B[i]) for i in range(H)]))

Submission status: Runtime Error

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

from collections import deque

q=deque([])
B=[[None]*H for _ in range (W)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.append((i,j))
            B[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while len(q)>0:
  XY=[]
  while len(q)>0:
     XY.append(q.popleft())
  for xy in XY:
    for i in range(4):
      if 0<=(xy[0]+dx[i])<=H-1 and 0<=(xy[1]+dy[i])<=W-1:
        if B[xy[0]+dx[i]][xy[1]+dy[i]]==None:
          B[xy[0]+dx[i]][xy[1]+dy[i]]=B[xy[0]][xy[1]]+1
          q.append((xy[0]+dx[i],xy[1]+dy[i]))
print(max([max(B[i]) for i in range(H)]))

Submission status: Runtime Error

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

import queue
q=queue.Queue()
B=[[None]*H for _ in range (W)]
cnt=0
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.put((i,j))
            B[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while q.empty()==False:
  XY=[]
  while q.empty()==False:
     XY.append(q.get())
  for xy in XY:
    for i in range(4):
      if 0<=xy[0]+dx[i]<=H-1 and 0<=xy[1]+dy[i]<=W-1:
        if B[xy[0]+dx[i]][xy[1]+dy[i]]==None:
          B[xy[0]+dx[i]][xy[1]+dy[i]]=B[xy[0]][xy[1]]+1
          q.put((xy[0]+dx[i],xy[1]+dy[i]))
print(max([max(B[i]) for i in range(H)]))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

f = open(sys.argv[1], "r")
input = f.readline

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

b = {}
check = set()
i = 0
for h in range(H):
    for c in input().strip():
        if c == "#":
            b[i] = 1
            check.add(i)
        i += 1
t = 0

#import time
#t1 = time.time()

while len(b) != W*H:
    t += 1
    tb = set()
    #print(len(check))
    for i in check:
        if i-W >= 0:
            tb.add(i-W)
        if i%W > 0:
            tb.add(i-1)
        if i%W < W-1:
            tb.add(i+1)
        if i+W < H*W:
            tb.add(i+W)
    check.clear()
    for i in tb:
        if i not in b:
            check.add(i)
        b[i] = 1
print(t)

#print(time.time()-t1)

Submission status: Runtime Error

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

import queue
q=queue.Queue()
B=[[0]*H for _ in range (W)]
cnt=0
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.put((i,j))
            B[i][j]=1
while sum([sum(B[k]) for k in range(H)])<H*W:
    new_q=[]
    while q.empty()==False:
        new_q.append(q.get())
    for t in new_q:
        if t[0]!=0:
            q.put((t[0]-1, t[1]))
            B[t[0]-1][t[1]]=1
        if t[0]!=H-1:
            q.put((t[0]+1, t[1]))
            B[t[0]+1][t[1]]=1
        if t[1]!=0:
            q.put((t[0], t[1]-1))
            B[t[0]][t[1]-1]=1
        if t[1]!=W-1:
            q.put((t[0], t[1]+1))
            B[t[0]][t[1]+1]=1
    cnt+=1
print(cnt)

Submission status: Runtime Error

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

B=[[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            B[i][j]=1
import copy
cnt=0
C=copy.copy(B)
while sum([sum(C[k]) for k in range(W)])<H*W:
    B=copy.deepcopy(C)
    cnt+=1
    for i in range(H):
        for j in range(W):
            if B[i][j]==1:
                if i>0:
                    C[i-1][j]=1
                if i<H-1:
                    C[i+1][j]=1
                if j>0:
                    C[i][j-1]=1
                if j<H-1:
                    C[i][j+1]=1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
L=[[0]*W for _ in range(W)]
next_q=deque()

for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            L[i][j]=1
            next_q.append((i,j))

q=deque()

res = 0
while len(next_q) != 0:
    q=copy.copy(next_q)
    next_q.clear()
    while q:
        y, x = q.popleft()
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q)==0: break
    res += 1
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
next_q=deque([(i, j) for i in range(H) for j in range(W) if A[i][j] == '#'])
L = [[0] * W for _ in range(H)]
q=deque()

res = 0
while len(next_q) != 0:
    q=next_q.copy()
    next_q.clear()
    while q:
        y, x = q.popleft()
        if y > 0 and L[y - 1][x] == 0:
            L[y - 1][x] = 1
            next_q.append((y - 1, x))
        if y < H - 1 and L[y + 1][x] == 0:
            L[y + 1][x] = 1
            next_q.append((y + 1, x))
        if x > 0 and L[y][x - 1] == 0:
            L[y][x - 1] = 1
            next_q.append((y, x - 1))
        if x < W - 1 and L[y][x + 1] == 0:
            L[y][x + 1] = 1
            next_q.append((y, x + 1))
    if len(next_q)==0: break
    res += 1
print(res)