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 sys import stdin, stdout

def main():
    N = (int)(stdin.readline())
    graph = dict()
	
    if N == 1:
      print("First")
      return
    if N == 2:
      print("Second")
      return
    
    for i in range(N-1):
        edge = stdin.readline().split()
        ai = (int)(edge[0])
        bi = (int)(edge[1])

        if ai in graph.keys():
            graph[ai].append(bi)
        else:
            graph[ai] = [bi]
        
        if bi in graph.keys():
            graph[bi].append(ai)
        else:
            graph[bi] = [ai]

    mid_node = bfs(graph, 1)[0]
    
    longest_path = bfs(graph, mid_node)[1]
    
    if longest_path % 3 == 1:
        print("Second")
    else:
        print("First")

def bfs(graph, node):

    result = -1
    last_level = set()
    visited = set()

    last_level.add(node)
    visited.add(node)

    length = 0

    while len(last_level) > 0:
        
        new_level = set()

        length += 1

        for last_node in last_level:
            result = last_node
            for neighbor in graph[last_node]:
                if neighbor not in visited:
                    new_level.add(neighbor)
                    visited.add(neighbor)
        last_level = new_level
    
    return result, length - 1

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
if all(all(j=="#" for j in list(a)) for i in a):
    print(0)
else:
    result = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == ".":
                q = deque([[i, j]])
                visit = [[-1 for _ in range(w)] for __ in range(h)]
                visit[i][j] = 0
                check = False
                while q:
                    y, x = q.popleft()
                    for s, t in [[-1,0],[1,0],[0,-1],[0,1]]:
                        if 0<=y+s and y+s<h and 0<=x+t and x+t<w:
                            if a[y+s][x+t]=="#":
                                result.append(visit[y][x]+1)
                                
                            elif visit[y+s][x+t]<0:
                                visit[y+s][x+t] = visit[y][x]+1
                                q.append([y+s,x+t])
    print(max(result))

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
if all(all(j=="." for j in list(a)) for i in a):
    print(0)
else:
    result = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == ".":
                q = deque([[i, j]])
                visit = [[-1 for _ in range(w)] for __ in range(h)]
                visit[i][j] = 0
                check = False
                while q:
                    y, x = q.popleft()
                    for s, t in [[-1,0],[1,0],[0,-1],[0,1]]:
                        if 0<=y+s and y+s<h and 0<=x+t and x+t<w:
                            if a[y+s][x+t]=="#":
                                result.append(visit[y][x]+1)
                                q = 0
                                break
                            elif visit[y+s][x+t]<0:
                                visit[y+s][x+t] = visit[y][x]+1
                                q.append([y+s,x+t])
    print(max(result))

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [input() for _ in range(h)]
result = []
for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            q = deque([[i, j]])
            visit = [[-1 for _ in range(w)] for __ in range(h)]
            visit[i][j] = 0
            check = False
            while q:
                y, x = q.popleft()
                for s, t in [[-1,0],[1,0],[0,-1],[0,1]]:
                    if 0<=y+s and y+s<h and 0<=x+t and x+t<w:
                        if a[y+s][x+t]=="#":
                            result.append(visit[y][x]+1)
                            q = 0
                            break
                        elif visit[y+s][x+t]<0:
                            visit[y+s][x+t] = visit[y][x]+1
                            q.append([y+s,x+t])

print(max(result))

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = []
graph = [[10000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (not check(x,y)) or (grid[y][x] == '#' and cost != 0):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            que.append([x+1,y,cost+1])
            que.append([x, y+1, cost+1])
            que.append([x-1,y,cost+1])
            que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = []
graph = [[10000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if (not check(x,y)):
            continue
        if (x,y) not in finished and graph[y][x] > cost:
            finished.add((x,y))
            graph[y][x] = cost
            que.append([x+1,y,cost+1])
            que.append([x, y+1, cost+1])
            que.append([x-1,y,cost+1])
            que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que = deque([(j,i,0)])
            bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate as acc
import operator as op
import copy as cp
import math
from bisect import bisect_left as bisl
from bisect import bisect_right as bisr
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
def nli(x):return [int(input()) for _ in range(x)]
def hukusuu():
  listA=[] #appendのために宣言が必要
  while True:
    try:listA.append(list(map(int,input().split())))
    except:break #または、quit(),os.exit()をして止める。
  return listA
def ifif(s):
  if s:print("Yes")
  else:print("No")




from collections import deque

import numpy as np
import sys
input = sys.stdin.readline
H , W =ma()
INF = H * W
S = np.array([[INF if i == '.' else 0 f0r i in input().strip()] for _ in range(H)])

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

print(np.max(S))

Submission status: Runtime Error

Solution code:
from collections import deque
from sys import stdin


def main():
    height, width = map(int, stdin.readline().split())
    q = deque([])
    grid = [stdin.readline() for _ in range(height)]
    distance = [[-1 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            if grid[i][j] == "#":
                q.append((i, j))
                distance[i][j] = 0
    answer = 0
    delta = ((0, 1), (1, 0), (0, -1), (-1, 0))
    while q:
        y, x = q.popleft()
        answer = distance[y][x]
        for dy, dx in delta:
            new_y = y + dy
            new_x = x + dx
            if 0 <= new_y < height and 0 <= new_x < width and grid[new_y][new_x] == ".":
                distance[new_y][new_x] = answer + 1
                grid[new_y][new_x] = "#"
                q.append((new_y, new_x))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append((i, j))
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cnt = -1
while q:
    cnt += 1
    qq = []
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or dist[yy][xx]:
                continue
            else:
                dist[yy][xx] = True
                qq.append((yy, xx))
    q = qq
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[False] * h for _ in range(w)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append((i, j))
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cnt = -1
while q:
    cnt += 1
    qq = []
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > h - 1 or yy > w - 1 or dist[yy][xx]:
                continue
            else:
                dist[yy][xx] = True
                qq.append((yy, xx))
    q = qq
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
a = [input() for i in range(h)]
q = []
dist = [[False] * h for _ in range(w)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append((i, j))
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
cnt = -1
while q:
    cnt += 1
    qq = []
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or dist[yy][xx]:
                continue
            else:
                dist[yy][xx] = True
                qq.append((yy, xx))
    q = qq
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
import copy

def main():
    h,w = (int(x) for x in input().split())
    field = [[j=='#' for j in input()] for _ in range(h)]

    que = deque([(i,j) for i in range(h) for j in range(w) if field[i][j]])

    dy, dx = [0,1,0,-1], [1,0,-1,0]
    cnt = 0
    while True:
        tque = deque()
        while que:
            y,x = que.popleft()
            for i in range(4):
                ny, nx = y+dy[i], x+dx[i]
                if ny < 0 and h <= ny: continue
                if nx < 0 and w <= nx: continue
                if field[ny][nx]: continue
                field[ny][nx] = True
                tque.append((ny,nx))

        if tque:
            que = copy.copy(tque)
            cnt += 1
        else:
            break
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for i in range(4):
            x1, x2 = x + dx[i], y + dy[i]
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
# from collections import deque
import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()
    # que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "#":
                que.put((i, j))
                # que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while len(que) > 0:

        now = que.get()
        # now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)
            # que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Runtime Error

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            # target = [now[0] + move_y, now[1] + move_x]
            target_y = now_y + move_y
            target_x = now_x + move_x
            # if not h > target[0] >= 0 or not w > target[1] >= 0:
            if not h > target_y >= 0 or not w > target_x >= 0:
                continue

            # 黒塗りされているなら何もしない
            # この条件、不要な気がする・・
            # if grid[target[0]][target[1]] == '#':
            #     continue

            # 距離が設定済みなら何もしない
            if not distance[target_y][target_x] == -1:
                continue

            # キューに追加
            que.put([target_y, target_x])

            # 最短距離を設定
            distance[target_y][target_x] = distance[now_y][now_x] + 1

	# 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = list(input())
        for j in range(w):
            grid[i][j] = line[j]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from collections import deque

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

q = deque()

for i in range(h):
    for j in range(w):
        if m[i][j] == '#':
            q.append((i,j))
            vm[i][j]=0

while q:
    y,x = q.popleft()
    d = vm[y][x]

    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        yi , xj = y + i , x + j
        if yi >= 0 and xj >= 0 and yi < h and xj < w and vm[yi][xj] == -1 :
            vm[yi][xj] = d +  1
            q.append([yi,xj])a

print(d)

Submission status: Runtime Error

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

from collections import deque
import numpy as np

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

for j in range(h):
    for i in range(w):
        a = field[j][i]
        if a=="#":
            q.append([j,i])
            d[j][i] = 0
        else:
            pass

def bfs(d):
    m = 0
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                m = max(m,d[ny][nx])
                q.append([ny,nx])
    return d,m

d,m = bfs(d)
print(m)

Submission status: Runtime Error

Solution code:
import queue 

H,W = map(int, input().split())
n_b = 0
m=[]
q = queue.Queue()

for i in range(H):
  m.append(list(input()))
  for j in range(W):
    if m[i][j]=="#":
      n_b += 1
      q.put([i,j])

n=0

while n_b != H*W:
  for i in range(H):
    for j in range(W):
      if m[i][j]=="#":
        # print("{} {}".format(i,j))
        q.put([i,j])

  while not q.empty():
    k,l=q.get()
    if l>0:
      if m[k][l-1]==".":
        m[k][l-1]="#"
        n_b+=1
    if l <H-1:
      if m[k][l+1]==".":
        m[k][l+1]="#"
        n_b+=1
    if k>0:
      if m[k-1][l]==".":
        m[k-1][l]="#"
        n_b+=1
    if k<W-1:
      if m[k+1][l]==".":
        m[k+1][l]="#"
        n_b+=1
  n+=1

print(n)

Submission status: Runtime Error

Solution code:
import queue 

H,W = map(int, input().split())
n_b = 0
m=[]
q = queue.Queue()

for i in range(H):
  m.append(list(input()))
  for j in range(W):
    if m[i][j]=="#":
      n_b += 1
      q.put([i,j])

n=0

while n_b != H*W:
  for i in range(H):
    for j in range(W):
      if m[i][j]=="#":
        q.put([i,j])

  while not q.empty():
    k,l=q.get()
    if l>0:
      m[k][l-1]="#"
      n_b+=1
    if l <H-1:
      m[k][l+1]="#"
      n_b+=1
    if k>0:
      m[k-1][l]="#"
      n_b+=1
    if k<W-1:
      m[k+1][l]="#"
      n_b+=1
  n+=1

print(n)

Submission status: Runtime Error

Solution code:
import queue 

H,W = map(int, input().split())
n_b = 0
m=[]
q = queue.Queue()

for i in range(H):
  m.append(list(input()))
  for j in range(W):
    if m[j]=="#":
      n_b += 1
      q.put([i,j])

n=0

while n_b != H*W:
  for i in range(H):
    for j in range(W):
      if m[i][j]=="#":
        q.put([i,j])

  while not q.empty():
    k,l=q.get()
    if l>0:
      m[k][l-1]="#"
      n_b+=1
    if l <H-1:
      m[k][l+1]="#"
      n_b+=1
    if k>0:
      m[k-1][l]="#"
      n_b+=1
    if k<W-1:
      m[k+1][l]="#"
      n_b+=1
  n+=1

print(n)

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                que.append((i, j))
                a[i][j] = 0

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

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((nx,ny))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

m = [list(map(lambda x: 1 if x=="#" else 0, input())) for _ in range(H)]
black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]

# print(m)
# print(black)

queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue_append((next_p[0], next_p[1], ans+1))
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
  H,W = map(int,input().split())
  maze = [list(input())for _ in range(H)]
  for i in range(H):
    for j in range(W):
      if maze[i][j]=="#":
        maze[i][j]=0
      else:
        maze[i][j]=float('INF')
  
  for i in range(1,H):
    maze[i,:]=np.minimum(maze[i,:],maze[i-1,:]+1)
  for i in range(H-2,-1,-1):
    maze[i,:]=np.minimum(maze[i,:],maze[i+1,:]+1)
  for i in range(1,W):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i-1]+1)
  for i in range(W-2,-1,-1):
    maze[:,i]=np.minimum(maze[:,i],maze[:,i+1]+1)
  print(np.max(maze))
main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for j in range(h):
    for i, c in enumerate(list(input().strip())):
      if c == '#':
        grids[w*i + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < w and 0 <= j+dy < h and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import numpy
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
INF = H * W
S = numpy.array([[INF if i == '.' else 0 for i in input().strip()] for _ in range(H)])

for h in range(1, H):
    S[h, :] = numpy.minimum(S[h,:],S[h-1,:] + 1)
for h in range(H - 2, -1, -1):
    S[h, :] = numpy.minimum(S[h,:],S[h+1,:] + 1)
for w in range(1, W):
    S[:, w] = numpy.minimum(S[:,w],S[:,w-1] + 1)
for w in range(w - 2, -1, -1):
    S[:, w] = numpy.minimum(S[:,w],S[:,w+1] + 1)

print(numpy.max(S))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [list(input().strip()) for _ in range(h)]
  dq = deque()
  for i in range(w):
    for j in range(h):
      if grids[i][j] == '#':
        dq.append((0, i, j))
  
  mcnt = -1
  while dq:
    cnt, i, j = dq.popleft()
    mcnt = cnt if cnt > mcnt else mcnt
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == '.':
        grids[i+dx][j+dy] = '#'
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
import numpy
from collections import deque
input = sys.stdin.readline

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

m = np.zeros(H, W)
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)

Submission status: Runtime Error

Solution code:
import numpy

H,W = map(int,input().split())
INF = H * W
S = numpy.array([[INF if i == '.' else 0 for i in input().strip()] for _ in range(H)])

for h in range(1, H):
    S[h, :] = numpy.minimum(S[h,:],S[h-1,:] + 1)
for h in range(H - 2, -1, -1):
    S[h, :] = numpy.minimum(S[h,:],S[h+1,:] + 1)
for w in range(1, W):
    S[:, w] = numpy.minimum(S[:,w],S[:,w-1] + 1)
for w in range(w - 2, -1, -1):
    S[:, w] = numpy.minimum(S[:,w],S[:,w+1] + 1)

print(numpy.max(S))

Submission status: Runtime Error

Solution code:
import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def f():
    q = collections.deque()
    dist = [[float("inf")] * W for _ in range(H)]
    for i in range(H):
        for k in range(W):
            if S[i][k] == '#':
                q.append((i,k))
                dist[i][k] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < W and w2 >= 0 and w2 < H:
                if dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
dist = f()
for i in range(H):
    for k in range(W):
        ans = max(ans,dist[i][k])
print(ans)

Submission status: Runtime Error

Solution code:
import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
brack_point = []
for i in range(H):
    for k in range(W):
        if S[i][k] == '#':
            brack_point.append([i,k])
def f(sx, sy, gx, gy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(H)] for h in range(W)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < W and w2 >= 0 and w2 < H:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
ans = 0
for i in range(H):
    for k in range(W):
        if S[i][k] == '.':
            tmp = float('inf')
            for point in brack_point:
                tmp = min(tmp,f(point[1],point[0],k,i))
            ans = max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
brack_point = []
for i in range(H):
    for k in range(W):
        if S[i][k] == '#':
            brack_point.append([i,k])
def f(sx, sy, gx, gy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(H)] for h in range(W)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < W and w2 >= 0 and w2 < H:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]
ans = 0
for i in range(H):
    for k in range(W):
        if S[i][k] == '.':
            tmp = float('inf')
            for point in brack_point:
                tmp = min(tmp,f(point[0],point[1],i,k))
            ans = max(ans,tmp)
print(ans)