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

def bfs(sy, sx):
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if a < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = a
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]
#maze = [list(input()) for i in range(H)]
slist = []
for i in range(H):
    #for j in range(W):
    maze[i] = list(input())
    if "#" in maze[i]
        slist.append((i, maze[i].index("#")))



for i in slist:
    s = bfs(i[0], i[1])

print(s)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np

def bfs(sy, sx):
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if a < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = a
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]
#maze = [list(input()) for i in range(H)]
slist = []
for i in range(H):
    for j in range(W):
        maze[i][j] = input()
        if maze[i][j]=="#":
            slist.append((i, j))



for i in slist:
    s = bfs(i[0], i[1])

print(s)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())

A = ['#' for i in range(W + 2)] + ['#' + input() + '#' for i in range(H)]+ ['#' for i in range(W + 2)]

B = [[A[i][j] == '#' for j in range(W + 2)] for i in range(H + 2)]


import collections
q = collections.deque()
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if B[i][j] == True:
            q.appendleft((i, j, 0))

while True:
    i, j, c = q.pop()
    if B[i - 1][j] == False:
        q.appendleft((i - 1, j, c + 1))
        B[i - 1][j] = True
    if B[i + 1][j] == False:
        q.appendleft((i + 1, j, c + 1))
        B[i + 1][j] = True
    if A[i][j - 1] == False:
        q.appendleft((i, j - 1, c + 1))
        B[i][j - 1] = True
    if B[i][j + 1] == False:
        q.appendleft((i, j + 1, c + 1))
        B[i][j + 1] = True


    if len(q) == 0:
        print(c)
        break


# A = [['#' for i in range(W + 2)]]\
#     + [list('#' + input() + '#') for i in range(H)]\
#     + [['#' for i in range(W + 2)]]
# import collections
# q = collections.deque()
# for i in range(1, H + 1):
#     for j in range(1, W + 1):
#         if A[i][j] == '#':
#             q.appendleft((i, j, 0))

# while True:
#     i, j, c = q.pop()
#     if A[i - 1][j] == '.':
#         q.appendleft((i - 1, j, c + 1))
#         A[i - 1][j] = '#'
#     if A[i + 1][j] == '.':
#         q.appendleft((i + 1, j, c + 1))
#         A[i + 1][j] = '#'
#     if A[i][j - 1] == '.':
#         q.appendleft((i, j - 1, c + 1))
#         A[i][j - 1] = '#'
#     if A[i][j + 1] == '.':
#         q.appendleft((i, j + 1, c + 1))
#         A[i][j + 1] = '#'


#     if len(q) == 0:
#         print(c)
#         break

Submission status: Runtime Error

Solution code:
from collections import deque

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

paint=((1,0),(-1,0),(0,1),(0,-1))
que=deque([])

dark=[[0]*W for _ in range(H)] # 1が黒、0はまだ白

for i in range(H): # 初期化(最初に黒いマスをdarkリストに入れて、キューに入れる。)
    for j in range(W):
        if S[i][j]=='#':
            que.append((i,j,0))
            dark[i][j]=1

while len(que)>0:
    di,dj,c=que.popleft()
    
    for pi,pj in paint:
        ni,nj=pi+di,pj+dj # 移動先がni,nj
        if 0<=ni<H and 0<=nj<W and dark[ni][nj]==0:
            dark[ni][nj]=1
            que.append((ni,nj,c+1))
            ans=c+1
print(ans)

Submission status: Runtime Error

Solution code:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    ans=0
    while True:
        Q = deque()
        cnt=0
        for i in range(h):
            for j in range(w):
                if l[j][i] == "#":
                    Q.append([i,j])
                    cnt+=1
        if cnt == h*w:
            return ans

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

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "#"

print(solve())

Submission status: Runtime Error

Solution code:
from collections import deque

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh, nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)

Submission status: Runtime Error

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

h, w = map(int, input().split())
a = np.array([[c for c in l.strip()] for l in sys.stdin])
q_x = deque()
q_y = deque()
b_plus = [[1,0],[-1,0],[0,1],[0,-1]]
dist = np.full((h,w),-1)

black = np.argwhere(a == '#')

for b in black:
    dist[b[0],b[1]] = 0
    for row in b_plus:
        b_n = b + row
        if 0<=b_n[0]<=w-1 and 0<=b_n[1]<=h-1:
            if not a[b_n[0],b_n[1]] == '#':
                a[b_n[0],b_n[1]] = '#'
                q_y.append(b_n[0])
                q_x.append(b_n[1])
                dist[b_n[0],b_n[1]] = dist[b[0],b[1]] +1

while (len(q_y)>0):
    v_y = q_y.popleft()
    v_x = q_x.popleft()
    for i in b_plus:
        nv_y = v_y + i[0]
        nv_x = v_x + i[1]
        if 0<=nv_y<=h-1 and 0<=nv_x<=w-1:
            if a[nv_y,nv_x] == '#':
                None
            elif not dist[nv_y,nv_x] == -1:
                None
            else:
                dist[nv_y,nv_x] = dist[v_y,v_x] + 1
                q_y.append(nv_y)
                q_x.append(nv_x)

print(int(np.amax(dist)))

Submission status: Runtime Error

Solution code:
from collections import deque
 
def main():
    h, w = map(int, input().split())
    maze= [list(input()) for i in range(h)]
    route = [[-1] * w for i in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if maze[i][j] == "#":
               que.append([i, j])
               route[i][j] = 0
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and route[nx][ny] == -1:
                route[nx][ny] = route[x][y] + 1
                que.append([nx, ny])

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

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
 
def main():
    h, w = map(int, input().split())
    maze= [list(input()) for i in range(h)]
    route = [[-1] * w for i in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               route[i][j] = 0
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and route[nx][ny] == -1:
                route[nx][ny] = route[x][y] + 1
                que.append([nx, ny])
                ans = max(ans , route[nx][ny])
#    ans = 0
#    for i in range(h):
#        for j in range(w):
#            ans = max(ans, d[i][j])
#    print(ans)
    
    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections

h, w = map(int, input().split())
a = [[""]*(w+2)]
for _ in range(h):
    _a = list(input())
    _a.append("")
    _a.insert(0, "")
    a.append(_a)
a.append([""]*(w*2))

visited = [[-float("inf")]*(w+2) for _ in range(h+2)]
init = []
for i in range(h+2):
    for j in range(w+2):
        if a[i][j] == "#":
            init.append([i, j])
            visited[i][j] = 0

q = collections.deque(init)

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

while 0 < len(q):
    cy, cx = q.pop()
    for _dx, _dy in zip(dx, dy):
        x = cx + _dx
        y = cy + _dy
        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for _v in visited:
    ans = max(ans, max(_v))

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

queue = deque()
for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '#':
            queue.append((i, j))

while queue:
    # 先頭の値を取り出す
    h, w = queue.popleft()

    # 上下左右4マスに対し処理
    for i in range(4):

        # 移動距離
        dx, dy = dis_x[i], dis_y[i]

        # もし次のマスが通路かつ黒塗りが終わっていないなら
        if s[h+dy][w+dx] == '.' and target_count != 0:
            s[h+dy][w+dx] = '#'
            dist[h+dy][w+dx] = dist[h][w] + 1
            target_count -= 1

            queue.append((h+dy, w+dx))


print(max(max(l) for l in dist))

Submission status: Runtime Error

Solution code:
import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not M[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not M[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not M[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not M[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([[i, j] for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and not M[nh][nw+1]:
        qq.append([nh,nw+1])
        M[nh][nw+1] = True
      if  0<=nw-1 and not M[nh][nw-1]:
        qq.append([nh,nw-1])
        M[nh][nw-1] = True
      if nh+1<=H-1 and not M[nh+1][nw]:
        qq.append([nh+1,nw])
        M[nh+1][nw] = True
      if 0<=nh-1 and not M[nh-1][nw]:
        qq.appenad([nh-1,nw])
        M[nh-1][nw] = True
    que = qq
  print(ans-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)]
dist = [[-1]*w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      que.append((i, j))
      dist[i][j] = 0
while que:
  y, x = que.popleft()
  for dy, dx in zip(di, dj):
    ny, nx = y+dy, x+dx
    if ny < 0 or ny >= h or nx < 0 or nx >= w:
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
ans = 0
for i in dist:
  ans = max(ans, i)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
h, w = map(int, input().split())
A = [input() for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      que.append((i, j))
      dist[i][j] = 0
while que:
  y, x = que.popleft()
  for dy, dx in zip(di, dj):
    ny, nx = y+dy, x+dx
    if ny < 0 or ny >= h or nx < 0 or nx >= w:
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
print(np.array(dist).max())

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[10**9]*w for i in range(h)]
q=deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
def bfs(maze,visited,q):
  ans=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==10**9:
          visited[newx][newy]=visited[x][y]+1
          q.append([newx,newy])
  for i in range(h):
    for i in range(w):
      ans=max(ans,visited[i][j])
  return ans
print(bfs(maze,visited,q))

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
q=deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
def bfs(maze,visited,q):
  ans=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
          visited[newx][newy]=visited[x][y]+1
          q.append([newx,newy])
  for i in range(h):
    for i in range(w):
      ans=max(ans,visited[i][j])
  return ans
print(bfs(maze,visited,q))

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
     
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = j, i
                d[sy][sx] = 0
                que.append((sy, sx))
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF:
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
                 
    return d

ans = 0
for l in bfs():
    ans = max(ans, max(l))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
grid=[]
for i in range(h):
	grid.append(input())
machines=deque()
visited=[[0 for i in range(h)] for j in range(w)]
for i in range(h):
	for j in range(w):
		if grid[i][j]=="#":
			machines.append((i,j))
			visited[i][j]=1

ans=0
while True:
	#print (visited)
	new=[]
	ans+=1
	while len(machines)!=0:
		c = machines.popleft()
		if c[0]>0:
			if visited[c[0]-1][c[1]]==0:
				visited[c[0]-1][c[1]]=1
				new.append((c[0]-1,c[1]))
		if c[0]<h-1:
			if visited[c[0]+1][c[1]]==0:
				visited[c[0]+1][c[1]]=1
				new.append((c[0]+1,c[1]))
		if c[1]>0:
			if visited[c[0]][c[1]-1]==0:
				visited[c[0]][c[1]-1]=1
				new.append((c[0],c[1]-1))
		if c[1]<w-1:
			if visited[c[0]][c[1]+1]==0:
				visited[c[0]][c[1]+1]=1
				new.append((c[0],c[1]+1))
	if len(new)==0:
		break
	else:
		temp=[]
		for i in new:
			temp.append(i)
		for i in range(len(temp)):
			machines.append(temp[i])
#print (visited)
print (ans-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
import numpy as np
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [list(input()) for i in range(h)]
b = np.zeros((h,w).dtype=int64)
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.append([i,j,0])
        else:
            b[i][j]=-1
"""
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and a[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and a[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and a[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and a[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)
"""

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
import numpy as np
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [list(input()) for i in range(h)]
b = np.zeros(h,w.dtype=int64)
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.append([i,j,0])
        else:
            b[i][j]=-1
"""
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and a[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and a[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and a[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and a[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)
"""

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            a[i][j]=0
            q.append([i,j,0])
        else:
            a[i][j]=-1
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and a[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and a[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and a[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and a[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h,w=map(int, input().split(' '))
a = [input() for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            a[i][j]=0
            q.append([i,j,0])
        else:
            a[i][j]=-1
while q:
    [s,t,cnt] = q.popleft()
    if s>0 and a[s-1][t] == -1:
        q.append([s-1,t,cnt+1])
        a[s-1][t] = cnt+1
    if s<h-1 and a[s+1][t] == -1:
        q.append([s+1,t,cnt+1])
        a[s+1][t] = cnt+1
    if t>0 and a[s][t-1] == -1:
        q.append([s,t-1,cnt+1])
        a[s][t-1] = cnt+1
    if t<w-1 and a[s][t+1] == -1:
        q.append([s,t+1,cnt+1])
        a[s][t+1] = cnt+1
ans = 0
for i in range(h):
    ans = max(ans,max(a[i]))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque 
H, W = map(int, input().split())
board = []
search_point = deque([])
min_distance_board = []
inf = 1000000000
for i in range(H):
    board.append(input())
    min_distance_board.extend([inf if point == '.' else 0 for point in board[i]])
    for j in range(len(board[i])):
        if board[i][j] == '#': search_point.extend([i, j, 0])

direction_list = [[1,0],[-1,0],[0,1],[0,-1]]
ans = 0
while search_point:
    now_point = search_point.popleft()
    for direction in direction_list:
        next_point = [now_point[0] + direction[0], now_point[1] + direction[1], now_point[2] + 1]
        if next_point[0] < 0 or next_point[0] >= H or next_point[1] < 0 or next_point[1] >= W \
        or min_distance_board[next_point[0]][next_point[1]] < inf:
            continue
        ans = max(next_point[2], ans)
        min_distance_board[next_point[0]][next_point[1]] = next_point[2]
        search_point.extend(next_point)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(W)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)

Submission status: Runtime Error

Solution code:
n,w = map(int,input().split())
lis = []
s = [str(input()) for i in range(h)]
for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      lis.append([i,j])
ans = 0
for i in range(h):
  for j in range(w):
    num = 10 ** 7
    for x,y in lis:
      num = min(num,abs(i-x)+abs(j-y))
    ans = max(ans,num)
print(ans)

Submission status: Runtime Error

Solution code:
from subprocess import call
call (('pypy3', '-c', """
from collections import deque

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

cnt = [[-1]*W for _ in range(H)]

que = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            que.append((h, w))
            cnt[h][w] = 0

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

print(int(ans))

Submission status: Runtime Error

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

black = []
distance = [[-1 for _ in range(H)] for _ in range(W)]
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))
      distance[i][j] = 0
      
while black:
  bi, bj = black.pop(0)
  for i, j in [(bi - 1, bj), (bi + 1, bj), (bi, bj - 1), (bi, bj + 1)]:
    if i >= 0 and i < H and j >= 0 and j < W:
      if M[i][j] == '.' and distance[i][j] == -1:
        M[i][j] = '#'
        black.append((i, j))
        distance[i][j] = distance[bi][bj] + 1
print(max([x for d in distance for x in d]))

Submission status: Runtime Error

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

black = []
distance = [[-1 for _ in range(H)] for _ in range(W)]
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))
      distance[i][j] = 0
      
while black:
  bi, bj = black.pop(0)
  for i, j in [(bi - 1, bj), (bi + 1, bj), (bi, bj - 1), (bi, bj + 1)]:
    if i >= 0 and i < H and j >= 0 and j < W:
      if M[i][j] == '.' and distance[i][j] == -1:
        M[i][j] = '#'
        black.append((i, j))
        distance[i][j] = distance[bi][bj] + 1
print(max([max(d) for d in distance]))

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
    global ans
    d = [[float("inf")] * w for _ in range(h)]
    que = deque([])
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append((i, j))
               d[i][j] = 0
            
    while que:
        p = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        i = 0
        while i < 4: 
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < w and 0 <= ny < h and A[nx][ny] != "#" and d[nx][ny] == float("inf"):
                d[nx][ny] = d[p[0]][p[1]] + 1
                A[nx][ny] = "#"
                que.append((nx, ny))
            i += 1
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])


h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
ans = 0
bfs()

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs():
    global ans
    que = deque([])
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append((i, j))
               d[i][j] = 0
            
    while que:
        p = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for k in range(len(que)):
            i = 0
            while i < 4: 
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]
                if 0 <= nx < w and 0 <= ny < h and A[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    A[nx][ny] = "#"
                    que.append((nx, ny))
                i += 1
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])


h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
d = [[float("inf")] * w for _ in range(h)]
ans = 0
bfs()

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def dfs(h,w,num):
    
    l[h][w]=min(l[h][w],num)
    
    if h>0:
        if A[h-1][w]!="#" and l[h-1][w]>num:
            dfs(h-1,w,num+1)
    if w>0:
        if A[h][w-1]!="#" and l[h][w-1]>num:
            dfs(h,w-1,num+1)
    if h<H-1:
        if A[h+1][w]!="#" and l[h+1][w]>num:
            dfs(h+1,w,num+1)
    if w<W-1:
        if A[h][w+1]!="#" and l[h][w+1]>num:
            dfs(h,w+1,num+1)
    
    return 0


A=[]
for _ in range(H):
    A.append(list(input()))

#print(A)

l=[[10**9]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            dfs(h,w,0)
ans=0
for item in l:
    ans=max(ans,max(item))

#print(l)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
  h,w=map(int,input().split())  
  mp=["#"*(w+2)]+["#"+input()+"#" for _ in range(h)]+["#"*(w+2)]
  dist=[-1]*((h+2)*(w+2))
  q=deque()
  
  for i in range(h+2):
    for j in range(w+2):
      if mp[i][j]=="#":
        q.append(i*w+j)
        dist[i*w+j]=0
      else:
        dist[i*w+j]=-1
  #print(q)
 
  while q:
    c=q.popleft()
    x=c//w
    y=c%w
    for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
      xx,yy=x+i,y+j
      tmp=xx*w+yy
      if dist[tmp]==-1:
        dist[tmp]=dist[c]+1
        q.append(tmp)
      
  print(max(dist))
  return

main()

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque

def main():


  h,w=map(int,input().split())
  field1=[list("#"*(w+2))]
  field2=[list("#"+input()+"#") for _ in range(h)]

  f=(field1+field2+field1)


  f=np.array(f)
  visited=np.array([[-1000]*(w+2) for _ in range(h+2)])

  slist=[]
  for i in range(1,w+1):
    for j in range(1,h+1):
      if f[i][j]=="#":
        slist.append((i,j))

  def dfs(maze,visited,slist):
    stack=deque([])
    for i,j in slist:
      visited[i][j]=0
      stack.append([i,j])

    while stack:
      x,y=stack.popleft()
      for i,j in ((1,0),(-1,0),(0,1),(0,-1)):
        x_new,y_new=x+i,y+j
        if maze[x_new][y_new]==".":# and visited[x_new][y_new]==-1000:
          visited[x_new][y_new]=visited[x][y]+1
          maze[x_new][y_new]="#"
          stack.append([x_new,y_new])

  dfs(f,visited,slist)      
  #print(f)
  print(visited.max())

main()