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: Accepted

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

from collections import deque
import heapq
import math
import bisect

H, W = map(int, input().split())
grid = [input() for i in range(H)]
dist = [[-1]*W for i in range(H)]
q = deque()
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]


def bfs():
    res = 0
    while(len(q)):
        ci, cj = q.popleft()
        for i in range(4):
            ni, nj = ci + dx[i], cj + dy[i]
            if 0<=ni<H and 0<=nj<W and dist[ni][nj]==-1:
                dist[ni][nj] = dist[ci][cj] + 1
                res = max(res, dist[ni][nj])
                q.append((ni, nj))

    return res


def main():
    for i in range(H):
        for j in range(W):
            if grid[i][j] == "#":
                dist[i][j] = 0
                q.append((i, j))

    print(bfs())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
A = [input() for i in range(H)]
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

INF = 99999
dp = [[INF]*W for i in range(H)]
q = deque()
for y,row in enumerate(A):
    for x,c in enumerate(row):
        if c=='#':
            dp[y][x] = 0
            q.append((x,y))

while q:
    x,y = q.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if dp[ny][nx] <= d+1: continue
        dp[ny][nx] = d+1
        q.append((nx,ny))
print(max(max(row) for row in dp))

Submission status: Runtime Error

Solution code:
def main():
    h, w = input_int_list()
    grid = []
    grid.append(["@"] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
    grid.append(["@"] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    cnt = 1
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    while True:
        do_swap = False
        # print("=====")
        # for line in grid:
        #     print(*line)
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if grid[i][j] == "#" or grid[i][j] == cnt - 1:
                    for di, dj in direction:
                        if grid[i + di][j + dj] == ".":
                            do_swap = True
                            grid[i + di][j + dj] = cnt
                    grid[i][j] = "@"
        if do_swap:
            cnt += 1
        else:
            break

    print(cnt - 1)

    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    H, W = NMI()
    grid = [SI() for _ in range(H)]
    step = [[-1]*W for _ in range(H)]
    que = deque()
    for h in range(H):
        for w in range(W):
            p = grid[h][w]
            if p == "#":
                que.append((h, w))
                step[h][w] = 0
    DIR = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    while que:
        x, y = que.popleft()

        for dx, dy in DIR:
            if not(0 <= x+dx < H and 0 <= y+dy < W):
                continue
            if step[x+dx][y+dy] >= 0:
                continue
            que.append((x+dx, y+dy))
            step[x+dx][y+dy] = step[x][y] + 1

    print(max(map(max, *step)))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline
H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = list(readline())
    for j,color in enumerate(A[i]):
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
            colors[i][j] = 0
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]

while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] >= 0 and mx > 0: continue
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
            colors[y][x] = op+1
print(mx)

Submission status: Runtime Error

Solution code:
W, H = map(int, input().split())
L = ["*" + input() +"*" for i in range(H)]
L = ["*" * (W + 2)] + L + ["*" * (W + 2)]
Q = [(i,j,0) for i in range(1, H + 1) for j in range(1, W + 1) if L[i][j] == "#"]
A = [[-2] + [-1] * W + [-2] for i in range(H)]
A = [[-2] * (W + 2)] + A + [[-2] * (W + 2)]
ans = 0
while len(Q) > 0:
  i, j, n = Q.pop(0)
  A[i][j] = n
  ans = max(ans, n)
  if A[i-1][j] == -1:
    Q.append([i-1, j, n + 1])
  if A[i+1][j] == -1:
    Q.append([i+1, j, n + 1])
  if A[i][j-1] == -1:
    Q.append([i, j-1, n + 1])
  if A[i][j+1] == -1:
    Q.append([i, j+1, n + 1])
print(ans)

Submission status: Runtime Error

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

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[x0][y0]:
                counts[x0][y0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Runtime Error

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

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[y0][x0]:
                counts[y0][x0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Runtime Error

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

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(w):
        a = input()
        for j in range(h):
            if a[j] == '#':
                q.append([i, j, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[y0+1][x0+1]:
                counts[y0+1][x0+1] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Runtime Error

Solution code:
import queue
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
q = queue.Queue()
INF = float('inf')
counts = [[INF]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[j][i] == '#':
            q.put([i, j, 0])
            counts[j][i] = 0
            
while not q.empty():
    x, y, z = q.get()
    ans = z
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x0 = x+i
        y0 = y+j
        if 0 <= x0 < w and 0 <= y0 < h:
            if counts[y][x]+1 < counts[y0][x0]:# and a[y0][x0] == '.':
                a[y0][x0] = '#'
                counts[y0][x0] = counts[y][x]+1
                q.put([x0, y0, counts[y0][x0]], z)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i in range(w) for j in range(h) if S[i][j]=='#']
    q = deque(q)
    ans = 0
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < h*w:
        ans += 1
        q_ = deque([])
        while len(q)>0:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i in range(w) for j in range(h) if S[i][j]=='#']
    q = deque(q)
    ans = 0
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < h*w:
        ans += 1
        q_ = deque()
        while len(q)>0:
            b = q.popleft()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    S[mv[0]][mv[1]]='#'
                    q_.append(mv)
        q = q_
        cnt += len(q)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

H,W = map(int,input().split())
D = [list(input()) for i in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        sy = i
        sx = j
        if D[sy][sx] == ".":
            Q = deque()
            Q.append((sx,sy))
            dist = [[-1]*W for i in range(H)]
            dist[sy][sx] = 0
            dx = [1,0,-1,0]
            dy = [0,-1,0,1]
            while Q:
                x,y = Q.popleft()
                if D[y][x] == "#":
                    d = dist[y][x]
                    ans = max(ans,d)
                    break
                for i in range(4):
                    nx = x+dx[i]
                    ny = y+dy[i]
                    if 0<=nx<=W-1 and 0<=ny<=H-1 and dist[ny][nx] == -1:
                        Q.append((nx,ny))
                        dist[ny][nx] = dist[y][x]+1

print(ans)

Submission status: Runtime Error

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

A=[list(str(input())) for i in range(H)]
#1<=sy<=R
d=[[-1 for j in range(W)]for i in range(H)]
inf=10**6
ans=0
queue=collections.deque()
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            queue.append([i,j])
            d[i][j]=0

moves=[[1,0],[-1,0],[0,1],[0,-1]]


while len(queue)>0:
    now=queue.popleft()
    for i in range(4):
        ny=now[0]+moves[i][0]
        nx=now[1]+moves[i][1]
        if 0<=ny and ny<H and 0<=nx and nx<W and A[ny][nx]=='.' and d[ny][nx]==-1:
            d[ny][nx]=d[now[0]][now[1]]+1
            queue.append([ny,nx])

nax=0
for i in range(H):
    for j in range(W):
        nax=max(nax,d[i][j])
print(nax)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
aa=[list(input()) for i in range(h)]
visited=[[0 for i in range(w)] for i in range(w)]
queue=[]
dy=[0,1,0,-1]
dx=[1,0,-1,0]
ans=0
for i in range(h):
    for j in range(w):
        if aa[i][j]=='#':
            queue.append([i,j])

while len(queue)>0:
    now=queue.pop(0)
    for i in range(4):
        x=now[1]+dx[i]
        y=now[0]+dy[i]
        if 0<=x<w and 0<=y<h:
            if visited[y][x]==0 and aa[y][x]=='.':
                queue.append([y,x])
                visited[y][x]=visited[now[0]][now[1]]+1
                ans=max(ans,visited[y][x])
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
h,w=map(int,input().split())
grid=[]
d=deque()
dist=[[-1]*w for i in range(h)]
di=[[0,1],[0,-1],[1,0],[-1,0]]
for i in range(h):
    arr=list(input())
    grid.append(arr)
for i in range(h):
    for j in range(w):
        if grid[i][j]=="#":
            d.append((i,j))
            dist[i][j]=0

while d:
    x,y=d.popleft()
    s=dist[y][x]
    for i,j in di:
        new_x=x+i
        new_y=y+j
        if new_x>=w or new_x<0 or new_y>=h or new_y<0 or dist[new_y][new_x]!=-1:
            continue
        dist[new_y][new_x]=s+1
        d.append((new_x,new_y))
print(s)

Submission status: Runtime Error

Solution code:
from collections import deque

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

#初期の黒の位置からの距離
dist = [[-1]*w for _ in range(h)] 

#黒の位置をキューに追加（複数スタート）
black_cells = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black_cells.append((h,w))
            dist[i][j] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h,w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1,0),(0,1),(-1,0),(0,-1)):
            new_h = h + dh
            new_w = w + dw
            if new_h <0 or h<=new_h or new_w <0 or w <= new_w:
                continue
            if dist[new_h][new_w] == -1: # セルがしろであるのと同意
                dist[new_h][new_w] = d+1
                
                black_cells.append((new_h,new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
a = [input() for i in range(h)]
b = [-1]*h*w; c = []; d = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#": b[i*w+j] = 0; c.append(i*w+j)
while len(c) < h*w:
    if c[d]//w != 0:
        if b[c[d]-w] == -1: b[c[d]-w] = b[c[d]]+1; c.append(c[d]-w)
    if c[d]%w != 0:
        if b[c[d]-1] == -1: b[c[d]-1] = b[c[d]]+1; c.append(c[d]-1)
    if c[d]%w != w-1:
        if b[c[d]+1] == -1: b[c[d]+1] = b[c[d]]+1; c.append(c[d]+1)
    if c[d]//w != w-1:
        if b[c[d]+w] == -1: b[c[d]+w] = b[c[d]]+1; c.append(c[d]+w)
    d += 1
print(max(b))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
seen = [[-1] * W for _ in range(H)]

from collections import deque

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

def bfs(maze, seen):
    while queue:
        y, x, c = queue.popleft()
        for i, j in [1, 0], [-1, 0], [0, 1], [0, -1]:
            dy = y + i
            dx = x + j
            if dy < 0 or H <= dy or dx < 0 or W <= dx:
                continue
            if seen[dy][dx] > -1:
                continue
            if maze[dy][dx] == '#':
                continue
            seen[dy][dx] = c + 1
            queue.append([dy, dx, c+1])

def check_max(seen):
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, seen[i][j])
    return ans
    
bfs(maze, seen)
print(check_max(seen))

Submission status: Runtime Error

Solution code:
'''
Created on 2020/08/25

@author: harurun
'''
from collections import deque
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  cnt=0
  H,W=map(int,pin().split())
  A=[]
  qx=deque([])
  qy=deque([])
  A.append(["b"]*(W+2))
  for i in range(H):
    a=list(pin()[:-1])
    A.append(["b"]+a+["b"])
    for j in range(W):
      if a[j]=="#":
        qx.append(i+1)
        qy.append(j+1)
  A.append(["b"]*(W+2))
  qx.append("cl")
  qy.append("cl")
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  while qx:
    nx=qx.popleft()
    ny=qy.popleft()
    if nx=="cl" and ny=="cl":
      if qx:
        qx.append("cl")
        qy.append("cl")
      cnt+=1
      continue
    for k in range(4):
      mx=nx+dx[k]
      my=ny+dy[k]
      if A[my][mx]==".":
        A[my][mx]="#"
        qx.append(mx)
        qy.append(my)
  print(cnt-1)
  return 
main()

Submission status: Runtime Error

Solution code:
'''
Created on 2020/08/25

@author: harurun
'''
def main():
  import queue
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  cnt=0
  H,W=map(int,pin().split())
  A=[]
  qx=queue.Queue()
  qy=queue.Queue()
  A.append(["b"]*(W+2))
  for i in range(H):
    a=list(pin()[:-1])
    A.append(["b"]+a+["b"])
    for j in range(W):
      if a[j]=="#":
        qx.put(i+1)
        qy.put(j+1)
  A.append(["b"]*(W+2))
  qx.put("cl")
  qy.put("cl")
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  n=0
  while not qx.empty() or not qy.empty():
    nx=qx.get()
    ny=qy.get()
    if nx=="cl" and ny=="cl" and n==0:
      qx.put("cl")
      qy.put("cl")
      cnt+=1
      n+=1
      continue
    n=0
    if nx=="cl" and ny=="cl":
      continue
    for k in range(4):
      mx=nx+dx[k]
      my=ny+dy[k]
      if A[my][mx]==".":
        A[my][mx]="#"
        qx.put(mx)
        qy.put(my)
  print(cnt-1)
  return 
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)]
    B = []

    for i,a in enumerate(A):
        for j,b in enumerate(a):
            if b == "#":
                B.append((i,j))

    dxy = [[1,0],[-1,0],[0,1],[0,-1]]

    stack = deque(B)
    darked = len(stack)
    targetd = h*w
    count = 0

    while darked < targetd:
        nextd = deque([])

        while stack:
            x, y = stack.popleft()
            for dx,dy in dxy:
                X = x + dx
                Y = y + dy
                if not(0 <= X < h) or not(0 <= Y < w):
                    continue
                if A[X][Y]==".":
                    A[X][Y]="#"
                    nextd.append((X,Y))
        count += 1
        stack = nextd
        darked += len(stack)
    print(count)
    
main()

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i + (w * j)] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i + (w * j)] < 0:
                dist[i + (w * j)] = dist[x + (w * y)] + 1
                que.append((i, j))
    return dist[x + (w * y)]


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

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i + (w * j)] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i + (w * j)] = dist[x + (w * y)] + 1
                que.append((i, j))
    return dist[x + (w * y)]


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

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i + (w * j)] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i + (w * j)] = dist[x + (w * y)] + 1
                que.append((i, j))
    return dist[x][y]


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

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w * h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i + (w * j)] = 0
                que.append((i, j)), frag.add((i, j))
    
    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i + (w * j)] = dist[x + (w * y)] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


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

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [-1] * (w + h)
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i + (h * j)] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i + (h * j)] = dist[i + (h * j)] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans))

Submission status: Runtime Error

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
ans = bfs(a)
print(max(max(ansi) for ansi in ans)

Submission status: Runtime Error

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

from collections import deque

seen = [[float("inf")] * w for _ in range(h)]
que = deque([])
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = []

for i in range(w):
    for j in range(h):
        if town[j][i] == "#":
            seen[j][i] = 0
            x = i
            y = j
            que.append((x, y))
while que:
    p, q = que.popleft()
    for dx, dy in direction:
            nx = p + dx
            ny = q + dy
            if 0 <= nx < w and 0 <= ny < h and town[ny][nx] != "#" and seen[ny][nx] == float('inf'):
                que.append((nx, ny))
                seen[ny][nx] = seen[q][p] + 1
                ans.append(seen[ny][nx])
print(max(ans))

Submission status: Runtime Error

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

from collections import deque

seen = [[float("inf")] * w for _ in range(h)]
que = deque([])
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(w):
    for j in range(h):
        if town[j][i] == "#":
            seen[j][i] = "0"
            x = i
            y = j
            que.append((x,y))
while que:
    p, q = que.popleft()
    for dx, dy in direction:
            nx = p + dx
            ny = p + dy
            if 0 <= nx < h and 0 <= ny < w and town[ny][nx] != "#" and seen[ny][nx] == float('inf'):
                que.append((nx, ny))
                seen[ny][nx] = seen[q][p] + 1

ans = max(list(map(lambda x: max(x), seen)))
print(ans)

Submission status: Runtime Error

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

from collections import deque

seen = [[float("inf")] * w for _ in range(h)]
que = deque([])
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(w):
    for j in range(h):
        if masu[j][i] == "#":
            seen[j][i] = "0"
            x = i
            y = j
            que.append((x,y))
while que:
    p, q = que.popleft()
    for dx, dy in direction:
            nx = p + dx
            ny = p + dy
            if 0 <= nx < h and 0 <= ny < w and town[ny][nx] != "#" and seen[ny][nx] == float('inf'):
                que.append((nx, ny))
                seen[ny][nx] = seen[q][p] + 1

ans = max(list(map(lambda x: max(x), seen)))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline().strip()

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

    def bfs(x,y,A):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
 
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= H or sy < 0 or sy >= W or A[sy][sx] == '#':
                    continue
                cnt = 1 if A[y][x] == '#' else A[y][x] + 1
                if A[sy][sx] == '.':
                    que.append((sx,sy))
                    A[sy][sx] = cnt
                elif A[sy][sx] > cnt:
                    que.append((sx,sy))
                    A[sy][sx] = cnt

    for x in range(W):
        for y in range(H):
            if A[y][x] == '#':
                bfs(x,y,A)
    ans = 0
    for a in A:
        a = [i if i != '#' else 0 for i in a]
        ans = max(ans,max(a))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

from collections import deque
q = deque()
reach = [[False]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append([i,j,0])
            reach[i][j] = True

ans = 0
while q:
    i,j,cnt = q.popleft()
    for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=i+k<w and 0<=j+l<h:
            if not reach[i+k][j+l]:
                q.append([i+k,j+l,cnt+1])
                reach[i+k][j+l] = True
    ans = max(ans,cnt)

print(ans)

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)]
    B = [(i, j) for i, a in enumerate(A) for j, b in enumerate(a) if b == '#']
    dxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    stack = deque(B)
    colored = len(B)
    tot = h * w
    count = 0
    while colored < tot:
        next = deque([])
        while stack:
            y, x = stack.popleft()
            for dx, dy in dxy:
                X = x + dx
                Y = y + dy
                if X < 0 or X >= w or Y < 0 or Y >= h:
                    continue
                if A[X][Y] == '.':
                    next.append((X, Y))
                    A[X][Y] = '#'
        stack = next
        count += 1
        colored += len(next)
    print(count)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    R,C = NMI()
    #sy, sx = NMI()
    #gy, gx = NMI()
    board = [list(input()) for _ in range(R)]
    
    ans = 0

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

    #すべての点をINFで初期化
    INF = R*C*2
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成
    que = deque([])
    
    #スタート地点を取り出す
    for r in range(R):
        for c in range(C):
            if board[r][c] == '#':
                que.append((r,c))
                #スタート地点の距離は0
                distance[r][c] = 0

    #queが空になるまでループ
    while len(que) != 0:
        #取り出してきた状態
        pop = que.popleft()

        #移動4方向をループ
        for i in range(len(dx)):
            #移動した後の点をny,nxとする
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]

            #nyが0以上R未満   nxが0以上C未満   まだ訪れたことがない
            if 0<= ny < R and 0 <= nx < C and　distance[ny][nx] == INF:
                #つまり移動可能でまだ行ったことがなければqueへ入れる
                que.append((ny,nx))
                #その距離をもとのpopの最短距離+1でdistanceに記録
                distance[ny][nx] = distance[pop[0]][pop[1]]+1
                if ans < distance[ny][nx]:
                    ans = distance[ny][nx]
                
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
grid = [["#"] * (W+2)]
for _ in range(H):
    grid.append(["#"] + list(sys.stdin.readline().strip()) + ["#"])
grid.append(["#"] * (W+2))
# print(grid)

q = deque()
for j in range(1, H+1):
    for i in range(1, W+1):
        if grid[i][j] == "#":
            q.append((i, j, 0))

ans = 0
while q:
    x, y, count = q.popleft()
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if grid[x+dx][y+dy] != ".":
            continue
        grid[x+dx][y+dy] = count + 1
        ans = count + 1
        q.append((x+dx, y+dy, count + 1))

# print(grid)
print(ans)