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:


H, W = map(int, input().split())
A = tuple(tuple(input()) for _ in range(H))
next_q = [(i, j) for i in range(H) for j in range(W) if A[i][j] == '#']
L = [[0] * W for _ in range(H)]

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
A=tuple(tuple(input()) for _ in range(H))
next_q=[]
L=[[0]*W for _ in range(H)]
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='#':
            next_q.append((i,j))
            L[i][j]=1
res=-1
while len(next_q)!=0:
    q,next_q=next_q[:],[]
    if len(q)==0:break
    while len(q)!=0:
        x,y=q.pop(0)
        if x>0 and L[x-1][y]==0:
            L[x-1][y]=1
            next_q.append((x-1,y))
        if x<W-1 and L[x+1][y]==0:
            L[x+1][y]=1
            next_q.append((x+1,y))
        if y>0 and L[x][y-1]==0:
            L[x][y-1]=1
            next_q.append((x,y-1))
        if y<H-1 and L[x][y+1]==0:
            L[x][y+1]=1
            next_q.append((x,y+1))
    res+=1
print(res)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
A=[tuple(input()) for _ in range(H)]
next_q=[]
L=[[0]*W for _ in range(H)]
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='#':
            next_q.append((i,j))
            L[i][j]=1
res=-1
while len(next_q)!=0:
    q,next_q=next_q[:],[]
    if len(q)==0:break
    while len(q)!=0:
        x,y=q.pop(0)
        if x>0 and L[x-1][y]==0:
            L[x-1][y]=1
            next_q.append((x-1,y))
        if x<W-1 and L[x+1][y]==0:
            L[x+1][y]=1
            next_q.append((x+1,y))
        if y>0 and L[x][y-1]==0:
            L[x][y-1]=1
            next_q.append((x,y-1))
        if y<H-1 and L[x][y+1]==0:
            L[x][y+1]=1
            next_q.append((x,y+1))
    res+=1
print(res)

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
A=[tuple(input()) for _ in range(H)]
q=[]
L=[[0]*W for _ in range(H)]
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='#':
            q.append((i,j))
            L[i][j]=-1
while len(q)!=0:
    x,y=q.pop(0)
    v=L[x][y]+1 if L[x][y]!=-1 else 1
    if x>0 and L[x-1][y]==0:
        L[x-1][y]=v
        q.append((x-1,y))
    if x<W-1 and L[x+1][y]==0:
        L[x+1][y]=v
        q.append((x+1,y))
    if y>0 and L[x][y-1]==0:
        L[x][y-1]=v
        q.append((x,y-1))
    if y<H-1 and L[x][y+1]==0:
        L[x][y+1]=v
        q.append((x,y+1))
print(max([max(l) for l in L]))

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
A=[tuple(input()) for _ in range(H)]
q=[]
L=[[0]*W for _ in range(H)]
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='#':
            q.append((i,j))
            L[i][j]=-1
print(q)
while len(q)!=0:
    x,y=q.pop(0)
    v=L[x][y]+1 if L[x][y]!=-1 else 1
    if x>0 and L[x-1][y]==0:
        L[x-1][y]=v
        q.append((x-1,y))
    if x<W-1 and L[x+1][y]==0:
        L[x+1][y]=v
        q.append((x+1,y))
    if y>0 and L[x][y-1]==0:
        L[x][y-1]=v
        q.append((x,y-1))
    if y<H-1 and L[x][y+1]==0:
        L[x][y+1]=v
        q.append((x,y+1))
print(max([max(l) for l in L]))

Submission status: Runtime Error

Solution code:
from queue import Queue

def bfs(start):
    global visited, time
    while start.qsize() > 0:
        hh, ww = start.get()
        time[hh][ww] = calc_min(hh, ww)
        visited[hh][ww] = 1
        h_w_list = [[hh + 1, ww], [hh, ww + 1], [hh - 1, ww], [hh, ww - 1]]
        for h_, w_ in h_w_list:
            if (h_ in range(h)) & (w_ in range(w)):
                if visited[h_][w_] == 0:
                    start.put([h_, w_])

def calc_min(hh, ww):
    h_w_list = [[hh + 1, ww], [hh, ww + 1], [hh - 1, ww], [hh, ww - 1]]
    for h_, w_ in h_w_list:
        if (h_ in range(h)) & (w_ in range(w)):
            min_num = min(time[hh][ww], time[h_][w_] + 1)
    return min_num

inf = 10 ** 9
h, w = map(int, input().split())
a = []
for hh in range(h):
    a.append(list(input()))
time = [[inf for _ in range(w)] for _ in range(h)]
start = Queue()
visited = [[0 for _ in range(w)] for _ in range(h)]
for hh in range(h):
    for ww in range(w):
        if a[hh][ww] == "#":
            start.put([hh, ww])
            time[hh][ww] = 0
bfs(start)
ans = max([max(c) for c in time])
print(ans)

Submission status: Runtime Error

Solution code:
# AGC033A - Darker and Darker
from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        0 0 0    1 1 1
        0 1 0 -> 1 0 1
        0 0 0    1 1 1
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = list(list(input()) for _ in range(h))
    B = [[1 if i == "#" else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    print(max(D))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque


H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]   # (i,j) = A[i][j]
seen = [[False] * W for _ in range(H)] 
queue = collections.deque([])

for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append((i,j,0))
            seen[i][j]=True

while queue:
    i,j,k=queue.popleft()
    if i!=0   and seen[i-1][j] == False: 
        queue.append((i-1,j,k+1))
        seen[i-1][j]=True
    if i!=H-1 and seen[i+1][j] == False:
        queue.append((i+1,j,k+1))
        seen[i+1][j]=True
    if j!=0   and seen[i][j-1] == False:
        queue.append((i,j-1,k+1))
        seen[i][j-1]=True
    if j!=W-1 and seen[i][j+1] == False:
        queue.append((i,j+1,k+1))
        seen[i][j+1]=True

print(k)

Submission status: Runtime Error

Solution code:
import numpy as np
h,w = [int(i) for i in input().split()]
maximum = h+w
value = []
for i in range(h):
  value.append([0 if i == "#" else maximum for i in input().split()])
values = np.array(value)
for x in range(w-1):
  values[:,x+1] = np.minimum(values[:,x]+1,values[:,x+1])
for x in range(w-1,0,-1):
  values[:,x-1] = np.minimum(values[:,x]+1,values[:,x-1])
for y in range(h-1):
  values[y+1,:] = np.minimum(values[y,:]+1,values[y+1,:])
for y in range(h-1,0,-1):
  values[y-1,:] = np.minimum(values[y,:]+1,values[y-1,:])
print(values.min())

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
board = [[0 if c=='.' else 1 for c in input()] for _ in range(h)]
cnt = sum(board)

iter = 0
while cnt < h*w:
  iter += 1
  for i in range(h):
    for j in range(w):
      if board[i][j] != iter:
        continue
      
      if i != 0:
        if board[i-1][j] == 0:
          cnt += 1
          board[i-1][j] = iter + 1
      
      if i != h-1:
        if board[i+1][j] == 0:
          cnt += 1
          board[i+1][j] = iter + 1
      
      if j != 0:
        if board[i][j-1] == 0:
          cnt += 1
          board[i][j-1] = iter + 1
      
      if j != w-1:
        if board[i][j+1] == 0:
          cnt += 1
          board[i][j+1] = iter + 1
            
print(iter)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
board = [[0 if c=='.' else '1' for c in input()] for _ in range(h)]
cnt = sum(board)

iter = 0
while cnt < h*w:
  iter += 1
  for i in range(h):
    for j in range(w):
      if board[i][j] != iter:
        continue
      
      if i != 0:
        if board[i-1][j] == 0:
          cnt += 1
          board[i-1][j] = iter + 1
      
      if i != h-1:
        if board[i+1][j] == 0:
          cnt += 1
          board[i+1][j] = iter + 1
      
      if j != 0:
        if board[i][j-1] == 0:
          cnt += 1
          board[i][j-1] = iter + 1
      
      if j != w-1:
        if board[i][j+1] == 0:
          cnt += 1
          board[i][j+1] = iter + 1
            
print(iter)

Submission status: Runtime Error

Solution code:
h, w = map(int, input()[:-1].split())
board = [[0 if c=='.' else '1' for c in input()] for _ in range(h)]
cnt = sum(board)

iter = 0
while cnt < h*w:
  iter += 1
  for i in range(h):
    for j in range(w):
      if board[i][j] != iter:
        continue
      
      if i != 0:
        if board[i-1][j] == 0:
          cnt += 1
          board[i-1][j] = iter + 1
      
      if i != h-1:
        if board[i+1][j] == 0:
          cnt += 1
          board[i+1][j] = iter + 1
      
      if j != 0:
        if board[i][j-1] == 0:
          cnt += 1
          board[i][j-1] = iter + 1
      
      if j != w-1:
        if board[i][j+1] == 0:
          cnt += 1
          board[i][j+1] = iter + 1
            
print(iter)

Submission status: Runtime Error

Solution code:
from sys import stdin

H, W = [int(x) for x in stdin.readline().rstrip().split()]
A = [stdin.readline().rstrip() for _ in range(H)]
B = [[A[x][y] for x in range(H)] for y in range(W)]
queue = []

for k in range(H):
    for l in range(W):
        if A[k][l] == '#':
            queue.append((k, l, 0))


while len(queue) > 0:
    h, w, t = queue.pop(0)
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            queue.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            queue.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            queue.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            queue.append((h, w + 1, t + 1))
    if len(queue) == 0:
        print(t)

Submission status: Runtime Error

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

def CHK(chk):
  tmp_queue=[]
  for j,i in chk:
    if A[j][i]=='.':
      A[j][i]='#'
      tmp_queue.append([j,i])
  return tmp_queue

def check(queue):
  chk=[]
  while len(queue)!=0:
    j,i=queue.pop(0)
    if j==0:
      if i==0:
        chk.append([j,i+1])
        chk.append([j+1,i])
      elif i==W-1:
        chk.append([j,i-1])
        chk.append([j+1,i])
      else:
        chk.append([j,i-1])
        chk.append([j,i+1])
        chk.append([j+1,i])
    elif j==H-1:
      if i==0:
        chk.append([j,i+1])
        chk.append([j-1,i])
      elif i==W-1:
        chk.append([j,i-1])
        chk.append([j-1,i])
      else:
        chk.append([j,i-1])
        chk.append([j,i+1])
        chk.append([j-1,i])
    else:
      if i==0:
        chk.append([j,i+1])
        chk.append([j+1,i])
        chk.append([j-1,i])
      elif i==W-1:
        chk.append([j,i-1])
        chk.append([j+1,i])
        chk.append([j-1,i])
      else:
        chk.append([j,i-1])
        chk.append([j,i+1])
        chk.append([j+1,i])
        chk.append([j-1,i])

  return CHK(chk)
     
queue=[]
p=0
while len(queue)!=0 or p==0:
  for j in range(H):
    for i in range(W):
      if A[j][i]=='#':
        queue.append([j,i])
  tmp_queue=check(queue)
  if len(tmp_queue)!=0:
    for tmp in tmp_queue:
      queue.append(tmp)
    p+=1

print(p)

Submission status: Runtime Error

Solution code:
import numpy as np

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

tile = []

for i in range(H):
    tile.append(list(input()))

tile = np.array(tile)

count = 0
while "." in tile:
    count += 1
    tmp = tile.copy()
    for (i, j), x in np.ndenumerate(tile):
        if x == "#":
            if i > 0:
                tmp[i-1, j] = "#"
            if j > 0:
                tmp[i, j-1] = "#"
            if i < W-1:
                tmp[i+1, j] = "#"
            if j < H-1:
                tmp[i, j+1] = "#"
        else:
            pass
    tile = tmp.copy()
    

print(count)

Submission status: Runtime Error

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

x = []

for _ in range(H):
    row = list( input() )
    x.append(row)

blacks = []
count = 0

for i in range(H):
    for j in range(W):
        a = x[i][j]
        if a == '#':
            count += 1
            blacks.append((i,j))

result = 0

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

while count < H*W:
    result += 1
    new_blacks = []
    for black in blacks:
        for dir in DIRS:
            i = black[0]+dir[0]
            j = black[1]+dir[1]
            if i < 0 or i >= H:
                continue
            if j < 0 or j >= H:
                continue
            if x[i][j] == '.':
                new_blacks.append((i,j))
                x[i][j] = '#'
                count += 1
    blacks = new_blacks

print(result)

Submission status: Runtime Error

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

x = []

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

blacks = []
count = 0

for i in range(H):
    for j in range(W):
        a = x[i][j]
        if a == '#':
            count += 1
            blacks.append((i,j))

result = 0

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

while count < H*W:
    result += 1
    new_blacks = []
    for black in blacks:
        for dir in DIRS:
            i = black[0]+dir[0]
            j = black[1]+dir[1]
            if i < 0 or i >= H:
                continue
            if j < 0 or j >= H:
                continue
            if x[i][j] == '.':
                new_blacks.append((i,j))
                x[i][j] = '#'
                count += 1
    blacks = new_blacks

print(result)

Submission status: Runtime Error

Solution code:
h,w = map( str, input().split() )

x = []

for _ in range(h):
    x.append = list(input())

blacks = []
count = 0

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

result = 0

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

while count < H*W:
    result += 1
    new_blacks = []
    for black in blacks:
        for dir in DIRS:
            i = black[0]+dir[0]
            j = black[1]+dir[1]
            if i < 0 or i >= H:
                continue
            if j < 0 or j >= H:
                continue
            if A[i][j] == '.':
                new_blacks.append((i,j))
                A[i][j] = '#'
                count += 1
    blacks = new_blacks

print(result)

Submission status: Runtime Error

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

l = []
for i, s in enumerate(a) :
    for j, c in enumerate(s) :
        if c == "#" :
            l.append([i, j])

ll = []
s = len(l)
ans = 0
while s != h*w :
    ans += 1
    for i, j in l :
        for y, x in [[1, 0], [0, 1], [-1, 0], [0, -1]] :
            if i+y<0 or h<=i+y :
                pass
            elif j+x<0 or h<=j+x :
                pass
            elif a[i+y][j+x] == "." :
                a[i+y][j+x] = "#"
                ll.append([i+y, j+x])
                s += 1
    l = list(ll)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

l = []
for i, s in enumerate(a) :
    for j, c in enumerate(s) :
        if c == "#" :
            l.append([i, j])

ll = []
s = len(l)
ans = 0
while s != h*w :
    ans += 1
    for i, j in l :
        for y, x in [[1, 0], [0, 1], [-1, 0], [0, -1]] :
            if i+y<0 or h<=i+y :
                pass
            elif j+x<0 or h<=j+x :
                pass
            elif a[i+y][j+x] == "." :
                a[i+y][j+x] = "#"
                ll.append([i+y, j+x])
                s += 1
    l = list(ll)

print(ans)

Submission status: Runtime Error

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint


INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

H, W = [int(x) for x in input().split()]
A = []
BQ = deque()
for _ in range(H):
    L = list(input())
    A.append(L)

for x in range(W):
    for y in range(H):
        if A[x][y] == '#':
            BQ.append((x, y))


def check(a):
    a2 = sum(a, [])
    cnt = a2.count('.')
    return cnt == 0


def ok(x, y, W, H):
    if x >= 0 and x < W and y >= 0 and y < H:
        return True
    return False


# X,Y座標
DX = [1, -1, 0, 0, 0]
DY = [0, 0, 1, -1, 0]

cnt = 0
while check(A) == False:
    newBQ = deque()
    for (x, y) in BQ:
        for (dx, dy) in zip(DX, DY):
            X = x + dx
            Y = y + dy
            if ok(X, Y, W, H) and A[X][Y] == '.':
                A[X][Y] = '#'
                newBQ.append((X, Y))
    cnt += 1
    BQ = newBQ

    # for a in A:
    #     print(a)
    # print("---")

print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
b=[]
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i,j])
  b.append(list(s))
count=0
while len(d)!=0:
  for i in range(len(d)):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]])
    if 0<x[0]
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]])
    if x[1]<w-1
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1])
    if 0<x[1]
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1])
  count+=1
print(count-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
d=deque()
for i in range(h):
  s=input()
  for j in range(w):
    if s[j]=="#":d.append([i,j])
  b.append(list(s))
count=0
while len(d)!=0:
  for i in range(len(d)):
    x=d.popleft()
    if x[0]<h-1:
      if b[x[0]+1][x[1]]==".":b[x[0]+1][x[1]]=count;d.append([x[0]+1,x[1]])
    if 0<x[0]
      if b[x[0]-1][x[1]]==".":b[x[0]-1][x[1]]=count;d.append([x[0]-1,x[1]])
    if x[1]<w-1
      if b[x[0]][x[1]+1]==".":b[x[0]][x[1]+1]=count;d.append([x[0],x[1]+1])
    if 0<x[1]
      if b[x[0]][x[1]-1]==".":b[x[0]][x[1]-1]=count;d.append([x[0],x[1]-1])
  count+=1
print(count-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000000)
 
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
 
            if 0<=nx<w and 0<=ny<h and d[nx][ny] == float("inf"):
                que.append((ny, nx))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000000)
 
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
 
            if 0<=nx<w and 0<=ny<h and d[ny][nx] == float("inf"):
                que.append((ny, nx))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
H, W = map(int,input().split())
S = [list(input()) for i in range(H)]
from collections import deque

q = deque()
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      S[i][j] = 0
      q.append([i,j])
C = []
while q:
  y, x = q.popleft()
  for k in [[1,0],[-1,0],[0,1],[0,-1]]:
    if not(0 <= y + k[0] < H):
      continue
    elif not(0 <= x + k[1] < W):
      continue
    elif S[y+k[0]][x+k[1]] != ".":
      continue
    else:
      S[y+k[0]][x+k[1]] = S[y][x]+1
      q.append([y+k[0],x+k[1]])
      C.append(S[y][x]+1)

print(max(C))

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000000)
 
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
 
            if 0<=nx<w and 0<=ny<h and d[nx][ny] == float("inf"):
                que.append((ny, nx))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

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

for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      S[i][j] = 0

C = []
for l in range(H+W):
  for i in range(H):
    for j in range(W):
      if S[i][j] == l:
        for k in [[1,0],[-1,0],[0,1],[0,-1]]:
          if not(0 <= i + k[0] < H):
            continue
          elif not(0 <= j + k[1] < W):
            continue
          elif S[i+k[0]][j+k[1]] != ".":
            continue
          else:
            S[i+k[0]][j+k[1]] = S[i][j]+1
            C.append(l)

print(max(C)+1)

Submission status: Runtime Error

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

for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      S[i][j] = 0

C = []
for l in range(H+W):
  for i in range(H):
    for j in range(W):
      if S[i][j] == l:
        for k in [[1,0],[-1,0],[0,1],[0,-1]]:
          if not(0 <= i + k[0] < H):
            continue
          elif not(0 <= j + k[1] < W):
            continue
          elif S[i+k[0]][j+k[1]] != ".":
            continue
          else:
            S[i+k[0]][j+k[1]] = S[i][j]+1
            C.append(l)

print(max(C)+1)

Submission status: Runtime Error

Solution code:
from collections import deque
 
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
 
            if 0<=nx<w and 0<=ny<h and d[nx][ny] == float("inf"):
                que.append((ny, nx))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(w):
        for j in range(h):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0<=nx<w and 0<=ny<h and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000)
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
def bfs():
    d = [[float("inf")] * w for i in range(h)]
    que = deque([])
    #黒だったらスタートキューに入れる
    for i in range(w):
        for j in range(h):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0<=nx<w and 0<=ny<h and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
                
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
count=0
def bfs():
    d = [[float("inf")] * w for i in range(h)]

    que = deque([])
    #黒だったらスタートキューに入れる
    for j in range(h):
        for i in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        global count
        p = que.popleft()
         # 黒にする4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0<=nx<w and 0<=ny<h and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int, input().split())  
s=[list(input()) for i in range(h)]
v=[]
count=0
def bfs():
    d = [[float("inf")] * w for i in range(h)]

    que = deque([])
    #黒だったらスタートキューに入れる
    for j in range(h):
        for i in range(w):
            if s[i][j]=='#':
                que.append((i, j))
                d[i][j]=0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    
    while que:
        global count
        p = que.popleft()
        #全部黒ならブレイク
        for i in range(h):
            count+=d[i].count(float('inf'))
        if count==0:
            break
         # 黒にする4方向をループ
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0<=nx<w and 0<=ny<h and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    for i in range(h):
        v.append(max(d[i]))
    return max(v)
res=bfs()
print(res)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan(my*w + mx) != 1000000:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan))
#print(saitan)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[False for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
for bx, by in B:
    check[bx][by] = 0

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

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] == False:
                lx, ly = nx, ny
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(check[lx][ly])