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


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = [list(input()) for i in hs]
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


hw = set(range(h*w))
for i in hw:
    d = d_list_update(d, h, w)
    if not d:
        break
ans = max([max(e) for e in memo])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = [input() for i in hs]
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


hw = set(range(h*w))
for i in hw:
    d = d_list_update(d, h, w)
    if not d:
        break
ans = max([max(e) for e in memo])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


hw = set(range(h*w))
for i in hw:
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
memo = [[-1] * w for j in range(h)]
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    counter[0] += 1
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
            if memo[dh + i][dw + j] == -1:
                memo[dh + i][dw + j] = memo[dh][dw] + 1
                d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


h, w = map(int, input().split())
time1 = time.time()
a = []
d = deque([])
memo = [[-1] * w for j in range(h)]
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
            if memo[dh + i][dw + j] == -1:
                memo[dh + i][dw + j] = memo[dh][dw] + 1
                d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
import sys


sys.setrecursionlimit(10000)
h, w = map(int, input().split())
a = []
d = deque([])
memo = [[-1]*w for j in range(h)]
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
            if memo[dh + i][dw + j] == -1:
                memo[dh + i][dw + j] = memo[dh][dw] + 1
                d.append([dh + i, dw + j])
    return d


def abc(d, hmax, wmax):
    d = d_list_update(d, hmax, wmax)
    if d:
        abc(d, hmax, wmax)
    return 0


abc(d, h, w)
ans = np.amax(np.array(memo))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
memo = [[-1]*w for j in range(h)]
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
            if memo[dh + i][dw + j] == -1:
                memo[dh + i][dw + j] = memo[dh][dw] + 1
                d.append([dh + i, dw + j])
    return d


def abc(d, hmax, wmax):
    d = d_list_update(d, hmax, wmax)
    if d:
        abc(d, hmax, wmax)
    return 0


abc(d, h, w)
ans = np.amax(np.array(memo))
print(ans)

Submission status: Runtime Error

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

class Toto():
    def __init__(self):
        self.count = 0

    def make_black(self):
        self.count += 1
        for h in range(H):
            for w in range(W):
                if A[h][w] == '#':
                    if w != 0:
                        A[h][w-1] = '#'
                    if w != W-1:
                        A[h][w+1] = '#'
                    if h != 0:
                        A[h-1][w] = '#'
                    if h != H-1:
                        A[h+1][w] = '#'
        self.check_hash()

    def check_hash(self):
        for a in A:
            for ta in a:
                if ta != '#':
                    self.make_black()
                    break
        else:
            print(self.count)

toto = Toto()
toto.check_hash()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    for j, c in enumerate(input()):
        if c == "#":
            status[i,j] = 0

for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)

print(np.max(status))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
 
#%% Smart Solution
 
input = sys.stdin.readline
 
H, W = map(int, input().split())
 
status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    for j, c in enumerate(input()):
        if c == "#":
            status[i,j] = 0
 
 
for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)
 
print(np.max(status))

Submission status: Runtime Error

Solution code:
import numpy as np

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

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            status[i,j] = 0

for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)

print(np.max(status))

Submission status: Runtime Error

Solution code:
import numpy as np

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

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            status[i,j] = 0

for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)

print(np.max(status))

Submission status: Runtime Error

Solution code:
import numpy as np

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

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            status[i,j] = 0

for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)

print(np.max(status))

Submission status: Runtime Error

Solution code:
import numpy as np
 
H, W = map(int, input().split())
 
status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            status[i,j] = 0
 
for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)
 
print(np.max(status))

Submission status: Runtime Error

Solution code:
def dig(tag,end):
    h=tag[0]
    w=tag[1]
    delta=[(1,0),(-1,0),(0,1),(0,-1)]
    next=set()
    for d in delta:
        if not h+d[0]<0 and not h+d[0]>=H and not w+d[1]<0 and not w+d[1]>=W and tag not in end:
            next.add((h+d[0],w+d[1]))
    return next

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

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            black_mass.add((h,w))

count=-1
end=set()
targets=black_mass
next_que=set()
while True:
    count+=1
    if count>5:
        exit(0)
    next_que=set()
    for tag in targets:
        next_que= next_que | dig(tag,end)
        end.add(tag)
    # print('next que',next_que)
    # print('end:',end)
    targets=next_que
    if len(end) == H*W:
        print(count)
        exit(1)

Submission status: Runtime Error

Solution code:
%load_ext Cython

%%cython
def test(int h, int w, wh, bl):
    mx = 0
    for i in wh:
        mn = h+w
        for j in bl:
            distance = abs(j[0]-i[0]) + abs(j[1]-i[1])
            if distance < mn:
                mn = distance
        if mn > mx:
            mx = mn
    return mx

if __name__ == '__main__':
    h, w = map(int, input().split())
    s = []
    for i in range(h):
        s.append(input().strip())

    bl = []
    wh = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                bl.append([i,j])
            else:
                wh.append([i,j])

    mx = test(int h, int w, wh, bl)
print(mx)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

todo = [[], []]

input = sys.stdin.readline
H, W = map(int, input().split())
field = np.zeros((H,W), dtype=int)

for i in range(H):
    for j, c in enumerate(input()):
        if c == '#':
            field[(i,j)] = 1
            todo[0].append((i,j))

def findAdjacent(loc):
    x, y = loc[0], loc[1]
    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
        if -1 < x+dx < W and -1 < y+dy < H:
            yield (x+dx, y+dy)

def colorAdjacent(loc, nxt):
    for l in findAdjacent(loc):
        if field[l] == 0:
            todo[nxt].append(l)
            field[l] += 1

ans = 0
while todo[0] or todo[1]:
    cur = ans % 2
    while todo[cur]:
        colorAdjacent(todo[cur].pop(), (cur+1)%2)
    ans += 1

print(ans-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""
 
# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = int(input()) for _ in range(N) # 1 row N column
 
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
 
def main():
    H, W = list(map(int,input().split()))
    A=[]
    for i in range(H):
        A.append(list(input()))
    ans=0
 
    white=True
	rangeh=range(H)
  	rangew=range(W)
    while white:
        white=False
        ans+=1
        A_next=[]
        for i in rangeh:
            B=[]
            for j in rangew:
                if A[i][j]!="#":
                    white=True
                    if i==0:
                        if j==0:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        elif j==W-1:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
 
                    elif i==H-1:
                        if j==0:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
 
                        elif j==W-1:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                    else:
                        if j==0:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
 
                        elif j==W-1:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                else:
                    B.append("#")
            A_next.append(B)
        A=A_next
    print(ans-1)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

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

cnt=0
while q:
    nq=[]
    for h,w in stack:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append([h+1,w])
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append([h-1,w])
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append([h,w+1])
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append([h,w-1])

    q=nq
    cnt+=1

print(cnt-1)

Submission status: Runtime Error

Solution code:
import copy

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, H, W, i, j):
    if i - 1 >= 0:
        A[i - 1][j] = '#'
    if i + 1 < H:
        A[i + 1][j] = '#'
    if j - 1 >= 0:
        A[i][j - 1] = '#'
    if j + 1 < W:
        A[i][j + 1] = '#'

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

count = 0
check_list = []
while True:
    if check_all(A, H, W):
        break
    B = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#' and (i, j) not in check_list:
                check_set.append((i, j))
                flip(B, H, W, i, j)
    A = B
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys

readline = sys.stdin.readline

H, W = map(int, readline().split())
a = tuple(readline() for _ in range(H))


def adjacent_vertices(v):
    r, c = divmod(v, H)

    if r > 0:
        yield v - H
    if r < H - 1:
        yield v + H
    if c > 0:
        yield v - 1
    if c < W - 1:
        yield v + 1


gen = (r * H + c for r in range(H) for c in range(W) if a[r][c] == '#')

# BFSで黒から最遠点までの距離を求める
dist = [-1] * (H * W)
q = deque()
for v in gen:
    dist[v] = 0
    q.append(v)
while q:
    v = q.popleft()
    d = dist[v]
    for nv in filter(lambda x: dist[x] == -1, adjacent_vertices(v)):
        dist[nv] = d + 1
        q.append(nv)

print(d)

Submission status: Runtime Error

Solution code:
from sys import stdin
H, W = stdin.readline().rstrip().split()
A = []
for i in range(int(H)): A.append(list(stdin.readline().rstrip()))
count = 0 # the number of operations 
white = "."
black = "#"
nWhite = 0

from collections import deque
queue = deque()

d = [[1000 for x in range(int(W))] for x in range(int(H))]

vx = [1, 0, -1, 0]
vy = [0, 1, 0, -1]
def bfs():
    count = 0
    for i in range(int(H)):
        for j in range(int(W)):
            if A[i][j] == black:
                queue.append([i,j]) 
                d[i][j] = 0
    while len(queue) > 0:
        temp = queue.popleft()
        x = temp[0]
        y = temp[1]
        for k in range(4):
            if x+vx[k] >= 0 and x+vx[k] < 6 and y+vy[k] >= 0 and y+vy[k] < 6 and A[x+vx[k]][y+vy[k]] == white:
                A[x+vx[k]][y+vy[k]] = black
                queue.append([x+vx[k], y+vy[k]])
                d[x+vx[k]][y+vy[k]] = d[x][y] + 1
                count = max(count, d[x+vx[k]][y+vy[k]])
    return count
print(str(bfs()))

Submission status: Runtime Error

Solution code:
H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()
T = input()

left = 1
right = W
up = 1
down = H

for i in reversed(range(N)):
    if i != N - 1:
        if T[i] == "U":
            if down != H:
                down -= 1
        elif T[i] == "D":
            if up != 1:
                up += 1
        elif T[i] == "L":
            if right != W:
                right += 1
        else:
            if left != 1:
                left -= 1
    if S[i] == "U":
        up -= 1
    elif S[i] == "D":
        down += 1
    elif S[i] == "L":
        left += 1
    else:
        right -= 1
    if left == right or up == down:
        print("NO")
        exit()
if left <= sr <= right and up <= sc <= down:
    print("YES")
else:
    print("NO")

Submission status: Runtime Error

Solution code:
from collections import deque

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

c = []
for i in range(H):
  c.append(list(input()))
  
dx = [1,0,-1,0]
dy = [0,1,0,-1]

s_list = []
for i in range (H):
    for j in range (W):
        if c[i][j] == '#':
            s_list.append([i,j])

que= deque()
d = [[float("inf") for i in range(W)] for j in range(H)]

for i in range (len(s_list)):
    que.append(s_list[i])
    d[s_list[i][0]][s_list[i][1]] = 0

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

      # 壁ではない＆未探索の判定
        if (0 <= next_y < H and 0 <= next_x < W) and c[next_y][next_x] != "#" and d[next_y][next_x] == float("inf"):
            que.append([next_y, next_x])
            d[next_y][next_x] = d[p[0]][p[1]] + 1

print(max(sum(ans,[])))

Submission status: Runtime Error

Solution code:
import math
import time
import pprint
import sys
from queue import Queue
from collections import deque
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while len(q) != 0:
        tmp_y, tmp_x = q.pop()
        for i in range(4):
            next_y = tmp_y + y_diff[i]
            next_x = tmp_x + x_diff[i]
            if ( 0 <= next_x <= w-1 
                    and 0 <= next_y <= h-1 
                    and check[next_y][next_x] == 0 
                    and a[next_y][next_x] != '#'):
                check[next_y][next_x] = 1 
                require[next_x][next_x] = require[tmp_y][tmp_x] + 1
                q.append([next_y, next_x])
    return require


h, w = MI()
a = [IS() for _ in range(h)]
start = time.time()
# h, w = 1000, 1000
# a = ['#.#.' * (w//4) for _ in range(h)]
out = 0
que = deque()

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

ans = bfs(que)

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

# print(time.time() - start)
print(out)

Submission status: Runtime Error

Solution code:
import math
import time
import pprint
import sys
from queue import Queue
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(start):
    q = Queue()
    for s in start:
        q.put(s)
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while q.qsize() != 0:
        tmp_x, tmp_y = q.get()
        for i in range(4):
            if ( 0 <= tmp_x + x_diff[i] <= w-1 
                    and 0 <= tmp_y + y_diff[i] <= h-1 
                    and check[tmp_x + x_diff[i]][tmp_y + y_diff[i]] == 0 
                    and a[tmp_x + x_diff[i]][tmp_y + y_diff[i]] != '#'):
                check[tmp_x + x_diff[i]][tmp_y + y_diff[i]] = 1 
                require[tmp_x + x_diff[i]][tmp_y + y_diff[i]] = require[tmp_x][tmp_y] + 1
                q.put([tmp_x + x_diff[i], tmp_y + y_diff[i]])
    return require


h, w = MI()
a = [IS() for _ in range(h)]
push = []
ans = [[INF for i in range(w)] for j in range(h)]
out = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            push.append([i,j])

ans = bfs(push)

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

print(out)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[False] * W for _ in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i][j] = True
      queue.append((i,j))
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if i > 0 and not dist_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if i < H-1 and not dist_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if j > 0 and not dist_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if j < W-1 and not dist_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Runtime Error

Solution code:
from queue import Queue
h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
black_num = sum([map_list[i].count("#") for i in range(h)])
ans = 0
q = Queue()
q1 = Queue()
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.put([y, x])
while (black_num < (h*w)):
    q_list = []
    for j in range(q.qsize()):
        y, x = q.get()
        if temp[y][x] == "#":
            for i in range(4):
                new_y = y + y_list[i]
                new_x = x + x_list[i]
                if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                    if map_list[new_y][new_x] == ".":
                        map_list[new_y][new_x] = "#"
                        black_num += 1
                        q_list.append([new_y, new_x])
    q = Queue()
    for qq in q_list:
        q.put(qq)
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
A = []
for i in range(H):
    A.append(list(input().split()[0]))
 
import numpy as np
indexes = list(map(list, np.array(np.where(np.array(A) == '#')).T))
 
cnt = 0
flag = False
 
if W == 1 and H == 1:
    flag = True
 
while not flag:
    for i, j in indexes:
        if i == 0 and j == 0:
            A[i + 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == 0 and j == W - 1:
            A[i + 1][j] = '#'
            A[i][j - 1] = '#'
        elif i == H - 1 and j == 0:
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == H - 1 and j == W - 1:
            A[i - 1][j] = '#'
            A[i][j - 1] = '#'
        elif i == 0:
            A[i + 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
        elif j == 0:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == H - 1:
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
        elif j == W - 1:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j - 1] = '#'
        else:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
    cnt += 1
    flag = all([all(np.array(A)[i] == '#') for i in range(len(A))])
    indexes = set(map(tuple, list(map(list, np.array(np.where(np.array(A) == '#')).T)))) - set(map(tuple, indexes))
 
print(cnt)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ.copy()

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(list(tmp))

que = deque()

for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que.copy()
while len(que) != H * W:
    tmp = next_que.copy()
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)