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:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    def dijkstra():
        while que:
            x, i, j = heappop(que)
            if x > dist[i][j]:
                continue
            for v in range(4):
                ni = i+di[v]
                nj = j+dj[v]
                if ni < 0 or ni >= h or nj < 0 or nj >= w:
                    continue
                push(ni, nj, x+1) 
    
    def push(i, j, x):
        if dist[i][j]<=x: return
        dist[i][j] = x
        heappush(que, (x, i, j))

    h, w = mi()
    inf = 10**18
    dist = [[inf]*w for _ in range(h)]
    que = []
    di = [-1, 0, 1, 0]
    dj = [0, 1, 0, -1]
    for i in range(h):
        for j, x in enumerate(input()):
            if x == '#':
                push(i, j, 0)
    dijkstra()
    ans = 0
    for i in range(h):
        for i in range(w):
            ans = max(ans, dist[i][j])
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,math,collections,itertools,copy
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = []
dot_cnt = 0
for _ in range(W):
    a = input().rstrip()
    dot_cnt += a.count('.')
    s.append(list(a))

numOpe = 0
while dot_cnt:
    numOpe += 1
    tmp = copy.deepcopy(s)
    for ih in range(H):
        for iw in range(W):
            if s[ih][iw]=='#':
                if (ih+1 != H) and (s[ih+1][iw]!='#')and(tmp[ih+1][iw]!='#'):
                    tmp[ih+1][iw]='#'
                    dot_cnt -=1
                elif(ih-1 != -1) and (s[ih-1][iw]!='#')and(tmp[ih-1][iw]!='#'):
                    tmp[ih-1][iw]='#'
                    dot_cnt -=1
                elif(iw+1 != W) and (s[ih][iw+1]!='#')and( tmp[ih][iw+1]!='#'):
                    tmp[ih][iw+1]='#'
                    dot_cnt -=1
                elif(iw-1 != -1) and (s[ih][iw-1]!='#')and(tmp[ih][iw-1]!='#'):
                    tmp[ih][iw-1]='#'
                    dot_cnt -=1        

    s = copy.deepcopy(tmp)
print(numOpe)

Submission status: Runtime Error

Solution code:
import sys,math,collections,itertools,copy
input = sys.stdin.readline

H,W=list(map(int,input().split()))
s = []
dot_cnt = 0
for _ in range(W):
    a = input().rstrip()
    dot_cnt += a.count('.')
    s.append(list(a))

numOpe = 0
while dot_cnt:
    numOpe += 1
    tmp = copy.deepcopy(s)
    for ih in range(H):
        for iw in range(W):
            if s[ih][iw] == '#':
                tmp[max(0,ih-1)][iw] = '#'
                tmp[min(ih+1,H-1)][iw] = '#'
                tmp[ih][max(0,iw-1)] = '#'
                tmp[ih][min(iw+1,W-1)] = '#'
    s = copy.deepcopy(tmp)
    dot_cnt=0
    for si in s:
        for sj in si:
            if sj =='.':
                dot_cnt = 1
                break
        if dot_cnt ==1:
            break
print(numOpe)

Submission status: Runtime Error

Solution code:
h, w = map(int,input().split(' '))
grid = []
for i in range(h):
  grid.append(list(input()))
  
black = []
for i in range(h):
  for j in range(w):
    if grid[i][j] == '#':
      black.append((i, j, 0))       

def bfs(grid):
  directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]   
  ans = 0
  while black:
    y, x, t = black.pop(0)
    for i, j in directions:
      if 0 <= x+i < w and 0 <= y+j < h and grid[x+i][y+j] == '.':
        grid[x+i][y+j] = '#'
        black.append((x+i, y+j, t+1))
        ans = max(ans, t+1)
  return ans
      
print(bfs(grid))

Submission status: Runtime Error

Solution code:
h, w = map(int,input().split(' '))
grid = []
for i in range(h):
  grid.append(list(input()))
  
black = []
for i in range(h):
  for j in range(w):
    if grid[i][j] == '#':
      black.append((i, j, 0))
      
directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]      
ans = 0

while black:
  y, x, t = black.pop(0)
  for i, j in directions:
    if 0 <= x+i < w and 0 <= y+j < h and grid[x+i][y+j] == '.':
      grid[x+i][y+j] = '#'
      black.append((x+i, y+j, t+1))
      ans = max(ans, t+1)
      
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int,input().split(' '))
grid = []
for i in range(h):
  grid.append(list(input()))
  
black = ()
for i in range(h):
  for j in range(w):
    if grid[i][j] == '#':
      black.append((i, j, 0))
      
directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]      
ans = 0

while black:
  y, x, t = black.pop(0)
  for i, j in directions:
    if 0 <= x+i < w and 0 <= y+j < h and grid[x+i][y+j] == '.':
      grid[x+i][y+j] = '#'
      black.append((x+i, y+j, t+1))
      ans = max(ans, t+1)
      
print(ans)

Submission status: Runtime Error

Solution code:
h, w = map(int,input().split(' '))
grid = []
for i in range(h):
  grid.append(list(input()))
  
black = []
for i in range(h):
  for j in range(w):
    if grid[i][j] == '#':
      black.append([i, j, 0])
      
directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]      
ans = 0

while black:
  y, x, t = black.pop(0)
  for i, j in directions:
    if 0 <= x+i < w and 0 <= y+j < h and grid[x+i][y+j] == '.':
      grid[x+i][y+j] = '#'
      black.append([x+i, y+j, t+1])
      ans = max(ans, t+1)
      
print(ans)

Submission status: Runtime Error

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

ans = 0
while True:
    A_next = [['' for _ in range(W)] for _ in range(H)]

    if all((A[y][x] == '#' for y in range(H) for x in range(W))):
        break

    for y in range(H):
        for x in range(W):
            if A[y][x] == '#':
                A_next[y][x] = '#'
            else:
                has_black = False
                if 0 <= y - 1:
                    has_black = has_black or A[y - 1][x] == '#'
                if y + 1 < H:
                    has_black = has_black or A[y + 1][x] == '#'
                if 0 <= x - 1:
                    has_black = has_black or A[y][x - 1] == '#'
                if x + 1 < H:
                    has_black = has_black or A[y][x + 1] == '#'
                if has_black:
                    A_next[y][x] = '#'
                else:
                    A_next[y][x] = '.'

    A = A_next
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
#これだとTLEするっぽい
from collections import deque
H, W = list(map(int, input().split()))

city = []

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

black_grid = []

for i in range(H):
    for j in range(W):
        if city[i][j] == "#":
            black_grid.append((i, j))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

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

for start in black_grid:
    sx, sy = start
    queue = deque()
    queue.append(start)
    dist[sy][sx] = 0

    while len(queue) > 0:
        now_x, now_y = queue.popleft()

        for dx_, dy_ in zip(dx, dy):
            adj_x = now_x + dx_
            adj_y = now_y + dy_

            if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
                continue

            if city[adj_y][adj_x] == "#":
                continue

            #初めてそのマスに到達する場合
            if dist[adj_y][adj_x] > H*W:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

            elif H*W > dist[adj_y][adj_x] > dist[now_y][now_x] + 1:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))


ans = -1
for i in range(H):
    for j in range(W):
        if dist[i][j] <= H*W:
            ans = max(dist[i][j], ans)

print(ans)

Submission status: Runtime Error

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

g = []

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

queue = deque()
for i in range(H):
    for j in range(W):
        if g[i][j] == "#":
            queue.append((i, j))

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

conter = 0
while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):
        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if g[adj_y][adj_y] == "#":
            continue

        if g[adj_y][adj_x] == ".":
            g[adj_y][adj_x] = "#"
            queue.append((adj_x, adj_y))

    counter += 1

print(counter)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    y= s[0]
    x= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    y= s[0]
    x= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= w or ny >= h:
            continue
        else:
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)

Submission status: Runtime Error

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

city = []

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

black_grid = []

for i in range(H):
    for j in range(W):
        if city[i][j] == "#":
            black_grid.append((i, j))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

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

for start in black_grid:
    sx, sy = start
    queue = deque()
    queue.append(start)
    dist[sy][sx] = 0

    while len(queue) > 0:
        now_x, now_y = queue.popleft()

        for dx_, dy_ in zip(dx, dy):
            adj_x = now_x + dx_
            adj_y = now_y + dy_

            if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
                continue

            if city[adj_y][adj_x] == "#":
                continue

            #初めてそのマスに到達する場合
            if dist[adj_y][adj_x] > H*W:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

            elif dist[adj_y][adj_x] > dist[now_y][now_x] + 1:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

ans = -1
for i in range(H):
    for j in range(W):
        if dist[i][j] <= H*W:
            ans = max(dist[i][j], ans)


print(ans)

Submission status: Runtime Error

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

city = []

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

black_grid = []

for i in range(H):
    for j in range(W):
        if city[i][j] == "#":
            black_grid.append((i, j))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

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

for start in black_grid:
    sx, sy = start
    queue = deque()
    queue.append(start)
    dist[sy][sx] = 0

    while len(queue) > 0:
        now_x, now_y = queue.popleft()

        for dx_, dy_ in zip(dx, dy):
            adj_x = now_x + dx_
            adj_y = now_y + dy_

            if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
                continue

            if city[adj_y][adj_x] == "#":
                continue

            #初めてそのマスに到達する場合
            if dist[adj_y][adj_x] > H*W:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

            if dist[adj_y][adj_x] > dist[now_y][now_x] + 1:
                dist[adj_y][adj_x] = dist[now_y][now_x] + 1
                queue.append((adj_x, adj_y))

ans = -1
for i in range(H):
    for j in range(W):
        if dist[i][j] <= H*W:
            ans = max(dist[i][j], ans)


print(ans)

Submission status: Runtime Error

Solution code:
from itertools import *
from collections import *
from sys import *
input=sys.stdin.readline
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if (nx,ny) not in q:
                    q.append((nx,ny))
aa=[]
for i in range(h):
    aa.append(max(ans[i]))
print(max(aa))

Submission status: Runtime Error

Solution code:
import sys
#import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

class queue:
	def __init__(self):
		self.l=list(1000*1000+100)
		self.f=0
		self.t=0
		
	def put(self,v):
		self.l[self.f]=v
		self.f+=1
		
	def get(self):
		self.t+=1
		return self.l[self.t-1]
		
	def empty(self):
		return self.f==self.t

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	mp = [list(input()) for _ in range(h)]
	dist=[[-1] * w for _ in range(h)]
	open_list=queue()
	for hi, l in enumerate(mp):
		for wi, c in enumerate(l):
			if c == '#':
				dist[hi][wi]=0
				open_list.put(hi*2000+wi)
				
	max_dist=0
	while not open_list.empty():
		hi_wi = open_list.get()
		hi = hi_wi // 2000
		wi = hi_wi % 2000
		d = dist[hi][wi]
		for dw, dh in [(0,1),(0,-1),(1,0),(-1,0)]:
			if -1 == wi+dw or -1 == hi + dh or w == wi+dw or h == hi + dh:
				continue
			if dist[hi+dh][wi+dw] >= 0:
				continue
			#if dist[hi+dh][wi+dw]==-2:
				
			dist[hi+dh][wi+dw]=d+1
			open_list.put(((hi+dh)*2000+wi+dw))
			max_dist=d+1
	print(max_dist)
	#for l in dist:
	#	print(l)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
from collections import deque
st=deque()
a=[]
b=[[0 for _ in range(w)] for _ in range(h)]
c=0

for i in range(h):
  a.append(input())
  for j in range(w):
    if a[i][j]=="#":
      st.append([i,j,1])
      b[i][j]=1

def dfs(x,y,i):
  d=[[0,1],[0,-1],[1,0],[-1,0]]
  for m in d:
    nx=x+m[0]
    ny=y+m[1]
    if (0<=nx<=w-1) and (0<=ny<=h-1) and b[nx][ny]==0:
      b[nx][ny]=1
      st.append([nx,ny,i+1])

while st:
  x,y,c=st.popleft()
  dfs(x,y,c)
print(c-1)

Submission status: Runtime Error

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


#-------------------------------------------------------------------------
#白から黒に変えていく

def search() :
    pos=deque([])


    D= [[True]*(W+2)]                                   #True True True True
    D+=[[True]+[False]*W+[True] for i in range(H)]      #True FalseFalseTrue
    D.append([True]*(W+2))                              #True True True True

    for i in range(H) :
        maze=input()
        for j in range(W) :
            if maze[j]=="#" :
                pos.append([i+1,j+1,0])
                D[i+1][j+1]=True
 
    while len(pos)>0 :
        h,w,depth=pos.popleft()
        for p,q in [[-1,0],[1,0],[0,-1],[0,1]] :
            if not D[h+p][w+q] :
                pos.append([h+p,w+q,depth+1])
                D[h+p][w+q]=True

    return depth            

#-------------------------------------------------------------------------
#動作
print(search())

Submission status: Runtime Error

Solution code:
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * ((H + 1) * (W + 1))
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                A[h * H + w] = True

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * H + ww]:
                    continue
                Q.put((hh, ww, d + 1))
                A[hh * H + ww] = True
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    H, W = read_values()
    F = [input().strip() for _ in range(H)]
    A = [False] * (H * W)
    Q = queue.Queue()

    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                Q.put((h, w, 0))
                A[h * H + w] = True

    res = V(max)
    while not Q.empty():
        h, w, d = Q.get()
        res.ud(d)

        for hh, ww in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= hh < H and 0 <= ww < W:
                if A[hh * H + ww]:
                    continue
                Q.put((hh, ww, d + 1))
                A[hh * H + ww] = True
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
    visited = [[0] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx]:
                visited[ny][nx] = min(visited[y][x] + 1,visited[ny][nx])
                Q.append((ny,nx))

    ans = 0
    for h in range(H):
        ans = max(ans, max(visited[h]))

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
    visited = [[0] * W for _ in range(H)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H and not visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                Q.append((ny,nx))

    ans = 0
    for h in range(H):
        ans = max(ans, max(visited[h]))

    print(ans)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(que,d): #幅優先探索
  "
  #いつもはここで定義
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  "
  lead = 0
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        #範囲外の場合
        continue
      if d[ny][nx]==float("inf"):
        d[ny][nx] = lead + 1
        que.append((ny,nx))
  return lead

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

#多点スタートなのでbfs()内で定義して初期化しない
d = [[float("inf")] * 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))
      #各"#"を入れる
      d[i][j] = 0

#print(bfs())
lead = bfs(que,d)
print(lead)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(que,d): #幅優先探索
  "
  #いつもはここで定義
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  "
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        #範囲外の場合
        continue
      if d[ny][nx]==float("inf"):
        d[ny][nx] = lead + 1
        que.append((ny,nx))
  return lead

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

#多点スタートなのでbfs()内で定義して初期化しない
d = [[float("inf")] * 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))
      #各"#"を入れる
      d[i][j] = 0

#print(bfs())
lead = bfs(que,d)
print(lead)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(que,d): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  lead = 0
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        continue
      if d[nx][ny]==float("inf"):
        d[nx][ny] = lead + 1
        que.append((nx,ny))
  return lead

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

d = [[float("inf")] * 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))
      d[i][j] = 0

#print(bfs())
lead = bfs(que,d)
print(lead)

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  lead = 0
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        continue
      if d[nx][ny]==float("inf"):
        d[nx][ny] = lead + 1
        que.append((nx,ny))
  return lead

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

d = [[float("inf")] * 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))
      d[i][j] = 0

print(bfs())

Submission status: Runtime Error

Solution code:
from collections import deque

def bfs(): #幅優先探索
  #入力のグラフを初期化
  #d = [[float("inf")] * w for i in range(h)] 
  #d == mazeリストの"."を"inf"に変えたリスト
  dx = [-1,0,0,1]
  dy = [0,-1,1,0]
  
  #que = deque([])
  #que.append((sx,sy))
  #d[sx][sy] = 0
  
  while que:
    lead_h,lead_w = que.popleft()
    lead = d[lead_h][lead_w]
    #lead == queの先頭にある要素を取り出す
    for i in range(4):
      nx = lead_w + dx[i]
      ny = lead_h + dy[i]
      if ny<0 or h<=ny or nx<0 or w<=nx:
        continue
      if d[nx][ny]==float("inf"):
        d[nx][ny] = lead + 1
        que.append((nx,ny))
  return lead

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

d = [[float("inf")] * 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))
      d[i][j] = 0

print(bfs())

Submission status: Runtime Error

Solution code:
def resolve():
    H, W = map(int, input().split())
    A, white = [], []
    for i in range(H):
        A.append(list(input()))
        if '.' in A[i]:
            for j in range(W):
                if A[i][j] == '.':
                    white.append([i, j])

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

    # 各白マスから黒マスまでの最短距離を探索し，その最大値を出力
    for sy, sx in white:
        dis = [[float('inf')] * W for _ in range(H)]
        dis[sy][sx] = 0
        q = deque([(sy, sx)])
        update = False
        while q:
            y, x = q.popleft()
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if (1
                        and 0 <= ny < H
                        and 0 <= nx < W
                        and dis[ny][nx] == float('inf')):
                    dis[ny][nx] = dis[y][x] + 1
                    q.append((ny, nx))
                    if A[ny][nx] == '#':
                        cnt = max(dis[ny][nx], cnt)
                        update = True
            if update:
                break
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
# p37 迷路の最短路

from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * n for i in range(m)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #queの定義
    que = deque([])
   
    for i in range(n):
        for j in range(m):
            # スタートとゴールの座標を探す
            if maze[i][j] == "#":
                sx = i
                sy = j
                que.append((sx, sy))
                d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    ans = 0
    for i in range(n):
        for j in range(m):
            ans = max(ans, d[i][j])
    
    return ans

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]

print(bfs())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

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

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

A = []
black_deque = deque()

for i in range(H):
    A.append(list(input()))
    black_deque.extend([(i,j) for j in range(W) if A[i][j] == '#'])

for x,y in black_deque:
    A[x][y] = 0

n_white = H*W-len(black_deque)
while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    tansaku = [(x+dx[k], y+dy[k]) for k in range(4)
        if 0 <= x+dx[k] < H and
           0 <= y+dy[k] < W and
           A[x+dx[k]][y+dy[k]] == '.'
    ]
    for new_x,new_y in tansaku:
        black_deque.append((new_x, new_y))
        n_while -= 1
        A[new_x][new_y] = depth+1
        if n_white == 0:
            print(depth+1)
            exit(0)

print(depth)