Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

d = 0
while len(black_cells) > 0:
    # キューとして使うのでpop()ではなくpopleft()
    h, w = black_cells.popleft()  # 黒いセルの座標
    d = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        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))

print(d)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

d = 0
while len(black_cells) > 0:
    # キューとして使うのでpop()ではなくpopleft()
    h, w = black_cells.popleft()  # 黒いセルの座標
    d = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        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))

print(d)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w])
            dist[h][w] = 0

d = 0
while len(black_cells) > 0:
    # キューとして使うのでpop()ではなくpopleft()
    h, w = black_cells.popleft()  # 黒いセルの座標
    d = dist[h][w]
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        new_h = h + dy
        new_w = w + dx
        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])

print(d)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w])
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while len(black_cells) > 0:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()  # 黒いセルの座標
        d = dist[h][w]
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            new_h = h + dy
            new_w = w + dx
            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:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w])
            dist[h][w] = 0

del grid

def bfs(black_cells, dist):
    ans = 0
    while len(black_cells) > 0:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()  # 黒いセルの座標
        d = dist[h][w]
        ans = max(ans, d)
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            new_h = h + dy
            new_w = w + dx
            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 ans

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w])
            dist[h][w] = 0

def bfs(grid, black_cells, dist):
    ans = 0
    while len(black_cells) > 0:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()  # 黒いセルの座標
        d = dist[h][w]
        ans = max(ans, d)
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            new_h = h + dy
            new_w = w + dx
            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 ans

ans = bfs(grid, black_cells, dist)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append([h, w])
            dist[h][w] = 0

def bfs(grid, black_cells, dist):
    ans = 0
    while len(black_cells) > 0:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()  # 黒いセルの座標
        d = dist[h][w]
        ans = max(ans, d)
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if grid[new_h][new_w] == '.':
                grid[new_h][new_w] = '#'
                black_cells.append([new_h, new_w])
                dist[new_h][new_w] = d+1
    return ans

ans = bfs(grid, black_cells, dist)
print(ans)

Submission status: Runtime Error

Solution code:
queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
queue = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])
# for i in range(H):
#     for j in range(W):
#         if field[i][j] == True:
#             queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)

Submission status: Runtime Error

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

matrix_list1 = []
matrix_list2 = []
cnt = 0

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

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            tap = [x+1,y]
            matrix_list2.append(tap)
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            tap = [x-1,y]
            matrix_list2.append(tap)
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            tap = [x,y+1]
            matrix_list2.append(tap)
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            tap = [x,y-1]
            matrix_list2.append(tap)
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Submission status: Runtime Error

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

matrix_list1 = []
matrix_list2 = []
cnt = 0

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

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            tap = [x+1,y]
            matrix_list2.append(tap)
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            tap = [x-1,y]
            matrix_list2.append(tap)
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            tap = [x,y+1]
            matrix_list2.append(tap)
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            tap = [x,y-1]
            matrix_list2.append(tap)
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
 
def main():
    h, w = map(int, input().split())
    G = [("#",)*(w+2)]+[("#",)+tuple(input())+("#",) for i in range(h)]+[("#",)*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    ans = 0
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()
 
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
                ans = max(ans, dist[ny][nx])
    print(ans)
if __name__ == "__main__":
    main()
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [("#",)*(w+2)]+[("#",)+tuple(input())+("#",) for i in range(h)]+[("#",)*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    ans = 0
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
                ans = max(ans, dist[ny][nx])
    print(ans)
if __name__ == "__main__":
    main()
提出情報

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline()
h, w = map(int, input().split())
fuchi = {}
kuro = {}
for i in range(h):
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            fuchi[(i, j)] = 1
            kuro[(i, j)] = 1

def add(poj):
    res = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if poj[0] == 0:
        res[0] = 0
    if poj[0] == h - 1:
        res[1] = 0
    if poj[1] == 0:
        res[2] = 0
    if poj[1] == w - 1:
        res[3] = 0
    return res

c = 0
size = 0

while(True):
    pojs = list(fuchi.keys())
    if len(kuro) == h * w:
        print(c)
        break
    for poj in pojs:
        fuchi.pop(poj)
        for item in add(poj):
            if item != 0:
                cand = (poj[0] + item[0], poj[1] + item[1])
                if cand not in pojs:
                    kuro[cand] = 1
                    fuchi[cand] = 1
    c += 1

Submission status: Runtime Error

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

l=[input() for _ in range(H)]


def bfs(H,W,l):
  max_a,max_b=0,0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a,b=x+dx[k],y+dy[k]
      if a>=0 and a<H and b>=0 and b<W and count[a][b]==-1:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
        if num==0:
          max_x,max_y=a,b
  return count[max_x][max_y]
print(bfs(H,W,l))

Submission status: Runtime Error

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

l=[input() for _ in range(H)]


def bfs(H,W,l):
  max_a,max_b=0,0
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a,b=x+dx[k],y+dy[k]
      if a>=0 and a<H and b>=0 and b<W and count[a][b]==-1:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
        if num==0:
          max_x,max_y=a,b
  return count[max_x][max_y]
print(bfs(H,W,l))

Submission status: Runtime Error

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

l=[input() for _ in range(H)]


def bfs(H,W,l):
  que=deque()
  count=[[-1]*W for _ in range(H)]
  num=H*W
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  for i in range(H):
    for j in range(W):
      if l[i][j]=='#':
        count[i][j]=0
        que.append([i,j])
        num-=1
  while num>0:
    x,y=que.popleft()
    for k in range(4):
      a, b=x+dx[k], y+dy[k]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1:
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
        num-=1
        max_x=a
        max_y=b
  return count[max_x][max_y]
print(bfs(H,W,l))

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
g=[]
for i in range(h):
    g.append(list(input()))
q=[]
v=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=='#':
            q.append([i,j])
            v[i][j]=1
ans=0
while len(q)>0:
    tmp=[]
    for i in q:
        a=i[0]
        b=i[1]
        if a==0:
            hi=[1]
        elif a==h-1:
            hi=[-1]
        else:
            hi=[1,-1]
        if b==0:
            wi=[1]
        elif b==w-1:
            wi=[-1]
        else:
            wi=[1,-1]
        for c in hi:
            if v[a+c][b]==0:
                tmp.append([a+c,b])
                v[a+c][b]=1
        for d in wi:
            if v[a][b+d]==0:
                tmp.append([a,b+d])
                v[a][b+d]=1
    q=tmp
    ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
g=[]
for i in range(h):
    g.append(list(input()))
q=[]
v=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if g[i][j]=='#':
            q.append([i,j])
            v[i][j]=1
ans=0
while len(q)>0:
    tmp=[]
    for i in q:
        a=i[0]
        b=i[1]
        if a==0:
            hi=[1]
        elif a==h-1:
            hi=[-1]
        else:
            hi=[1,-1]
        if b==0:
            wi=[1]
        elif b==w-1:
            wi=[-1]
        else:
            wi=[1,-1]
        for c in hi:
            for d in wi:
                if v[a+c][b+d]==0:
                    tmp.append([a+c,b+d])
                    v[a+c][b+d]=1
    q=tmp
    ans+=1
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

queue = deque([])
Distance = [[-1 for i in range(w)]for j in range(h)]

for i in range(h):
  for j in range(w):
    if A[i][j]=='#':
      queue.append([i,j])
      Distance[i][j] = 0

while queue:
    x,y = queue.popleft()
    if x!=0:
        if A[x-1][y] == '.' and Distance[x-1][y] == -1:
            queue.append([x-1,y])
            ans = Distance[x-1][y] = Distance[x][y] + 1
    if x!=h-1:
        if A[x+1][y] == '.' and Distance[x+1][y] == -1:
            queue.append([x+1,y])
            ans = Distance[x+1][y] = Distance[x][y] + 1
    if y!=0:
        if A[x][y-1] == '.' and Distance[x][y-1] == -1:
            queue.append([x,y-1])
            ans = Distance[x][y-1] = Distance[x][y] + 1
    if y!=w-1:
        if A[x][y+1] == '.' and Distance[x][y+1] == -1:
            queue.append([x,y+1])
            ans = Distance[x][y+1] = Distance[x][y] + 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

class Grid():
    def __init__(self,i,j,isblack):
        self.i=i
        self.j=j
        self.isblack=isblack
        self.distance=0
    def __str__(self):
        print(f'i={i},j={j},isblack={isblack},distance={distance}')

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

g=[]
for i in range(H):
    Ai=input()
    gi=[]    
    for j in range(W):
        gi.append(Grid(i,j,Ai[j]=='#'))
    g.append(gi)

d=deque()

# 黒マスのreachedをTrueにし，dequeに入れる
for row in g:
    for grid in row:
        if grid.isblack:
            d.append(grid)

while d:
    tg=d.popleft()
    i=tg.i
    j=tg.j
    if i>0 and not g[i-1][j].isblack:
        g[i-1][j].isblack=True
        g[i-1][j].distance=tg.distance+1
        d.append(g[i-1][j])
    if i<H-1 and not g[i+1][j].isblack:
        g[i+1][j].isblack=True
        g[i+1][j].distance=tg.distance+1
        d.append(g[i+1][j])
    if j>0 and not g[i][j-1].isblack:
        g[i][j-1].isblack=True
        g[i][j-1].distance=tg.distance+1
        d.append(g[i][j-1])
    if j<W-1 and not g[i][j+1].isblack:
        g[i][j+1].isblack=True
        g[i][j+1].distance=tg.distance+1
        d.append(g[i][j+1])

'''
for row in g:
    for grid in row:
#        print(grid.distance,end=' ')
#    print()
'''

print(max([max([grid.distance for grid in row]) for row in g]))

Submission status: Runtime Error

Solution code:
INF=1999
H,W=map(int,input().split())
A=[]
for i in range(H):
    A.append(input())
c=[[INF for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            c[i][j]=0
            l=1
            while i-l>=0 and A[i-l][j]=='.':
                c[i-l][j]=min(c[i-l][j],l)
                l+=1
            r=1
            while i+r<=W-1 and A[i+r][j]=='.':
                c[i+r][j]=min(c[i+r][j],r)
                r+=1
            u=1
            while j-u>=0 and A[i][j-u]=='.':
                c[i][j-u]=min(c[i][j-u],u)
                u+=1
            d=1
            while j+d<=H-1 and A[i][j+d]=='.':
                c[i][j+d]=min(c[i][j+d],d)
                d+=1

for i in range(H):
    for j in range(W):
        if 0<c[i][j]<INF:
            l=1
            while i-l>=0 and A[i-l][j]=='.':
                c[i-l][j]=min(c[i-l][j],c[i][j]+l)
                l+=1
            r=1
            while i+r<=W-1 and A[i+r][j]=='.':
                c[i+r][j]=min(c[i+r][j],c[i][j]+r)
                r+=1
            u=1
            while j-u>=0 and A[i][j-u]=='.':
                c[i][j-u]=min(c[i][j-u],c[i][j]+u)
                u+=1
            d=1
            while j+d<=H-1 and A[i][j+d]=='.':
                c[i][j+d]=min(c[i][j+d],c[i][j]+d)
                d+=1

ans=max([max(c[i]) for i in range(H)])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque

H, W = map(int, input().split())
M = [list(input()) for i in range(H)]
reached = [[False for i in range(W)] for j in range(H)]
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]

nq = deque()
for y in range(H):
  for x in range(W):
    if M[y][x] == '#':
      nq.append((x, y))

res = 0
while len(nq) > 0:
  q = nq.copy()
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in nexts:
      nx, ny = x+dx, y+dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        continue
      if M[ny][nx] == '#' or reached[ny][nx]:
        continue
      nq.append((nx, ny))
      reached[ny][nx] = True
  if len(nq) > 0:
    res += 1

print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
# +1周分だけ
black = np.zeros((H+2,W+2),dtype=np.bool)
# \nがあることに注意
black[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'#').reshape(H,W+1)

INF = 10 ** 4
dist = np.zeros((H,W),dtype=np.int8)
# .のところは０それ以外はINFで初期化
dist[~black[1:-1,1:-1]] = INF
# 右、左、下、上と展開させていく感じ
for n in range(1,H):
    np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(H-2,-1,-1):
    np.minimum(dist[n+1]+1,dist[n],out=dist[n])
for n in range(1,W):
    np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(W-2,-1,-1):
    np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

print(dist.max())

Submission status: Runtime Error

Solution code:
def main():
    buf = sys.stdin.buffer
    R,C = map(int,buf.readline().split())
    # \nが含まれるから列要素の数が+1
    black = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#')
    sharps = np.where(black==True)[0]

    coord_x = np.array([[j for i in range(C)] for j in range(R)])
    coord_y = np.array([[i for i in range(C)] for j in range(R)])

    sharps = sharps[sharps%(C+1)!=C]

    sharps_x = sharps//(C+1)
    sharps_y = sharps%(C+1)
    for i,(one_sharp_x,one_sharp_y) in enumerate(zip(sharps_x,sharps_y)):
        #one_sharp_x = one//(C+1)
        #one_sharp_y = one%(C+1)
        if i == 0:
            result_np = abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y)
        else:
            result_np = np.minimum(result_np,abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y))

    print(max(result_np.flatten()))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

def main()
buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
# \nが含まれるから列要素の数が+1
black = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#')
sharps = np.where(black==True)[0]

coord_x = np.array([[j for i in range(C)] for j in range(R)])
coord_y = np.array([[i for i in range(C)] for j in range(R)])

sharps = sharps[sharps%(C+1)!=C]

sharps_x = sharps//(C+1)
sharps_y = sharps%(C+1)
for i,(one_sharp_x,one_sharp_y) in enumerate(zip(sharps_x,sharps_y)):
    #one_sharp_x = one//(C+1)
    #one_sharp_y = one%(C+1)
    if i == 0:
        result_np = abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y)
    else:
        result_np = np.minimum(result_np,abs(coord_x-one_sharp_x) + abs(coord_y-one_sharp_y))

print(max(result_np.flatten()))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
m = ["" for _ in range(H)] 
import queue
q = queue.Queue()

#sharps = []
for i in range(H):
    m[i] = input()
    for j in enumerate(m[i]):
        if j[1] == "#":
            q.put((i,j[0]))
            
times_map = [0] * (H*W)
bool_map = [0]* (H*W)

counter = -1
while sum(bool_map) != H*W:
    counter +=1
    sharps = [q.get() for _ in range(q.qsize())]
    for one in sharps:
        if one[0] < 0 or one[0] >= H or one[1] < 0 or one[1] >= W:
            continue
        index = one[0]*(H)+one[1]
        if bool_map[index] == 0:
            times_map[index] = counter
            bool_map[index] = 1
            q.put((one[0]+1,one[1]))
            q.put((one[0]-1,one[1]))
            q.put((one[0],one[1]+1))
            q.put((one[0],one[1]-1))
            
print(counter)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
m = ["" for _ in range(H)] 
import queue
import numpy as np
q = queue.Queue()

#sharps = []
for i in range(H):
    m[i] = input()
    for j in enumerate(m[i]):
        if j[1] == "#":
            q.put((i,j[0]))
            
times_map = np.zeros(H*W)
bool_map = np.zeros(H*W)

counter = -1
while sum(bool_map) != H*W:
    counter +=1
    sharps = [q.get() for _ in range(q.qsize())]
    for one in sharps:
        if one[0] < 0 or one[0] >= H or one[1] < 0 or one[1] >= W:
            continue
        index = one[0]*(H)+one[1]
        if bool_map[index] == 0:
            times_map[index] = counter
            bool_map[index] = 1
            q.put((one[0]+1,one[1]))
            q.put((one[0]-1,one[1]))
            q.put((one[0],one[1]+1))
            q.put((one[0],one[1]-1))
            
print(counter)

Submission status: Runtime Error

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

q = set()

def encode(i, j):
    return i*w + j

def decode(x):
    i = x // w
    j = x % w
    return [i, j]

for i in range(1, h+1):
    for j in range(1, w+1):
        if a[i][j] == '#':
            q.add(encode(i, j))

for ans in range(h+w):
    nq = set()
    for x in q:
        i, j = decode(x)
        for k in [-1,1]:
            if a[i+k][j] == '.':
                nq.add(encode(i+k, j))
                a[i+k][j] = '#'
        for k in [-1,1]:
            if a[i][j+k] == '.':
                nq.add(encode(i, j+k))
                a[i][j+k] = '#'
    if len(nq) == 0:
        print(ans)
        exit()
    else:
        q = set()
        q = q | nq

Submission status: Runtime Error

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def fill(queue):
        footsteps = [[None] * width for _ in range(height)]
        for p, s in queue:
            footsteps[p[1]][p[0]] = -1

        while queue:
            p, s = queue.popleft()
            x, y = p
            footsteps[y][x] = s

            if x > 0 and footsteps[y][x - 1] is None:
                queue.append(((x - 1, y), s + 1))
                footsteps[y][x - 1] = -1
            if x < width - 1 and footsteps[y][x + 1] is None:
                queue.append(((x + 1, y), s + 1))
                footsteps[y][x + 1] = -1
            if y > 0 and footsteps[y - 1][x] is None:
                queue.append(((x, y - 1), s + 1))
                footsteps[y - 1][x] = -1
            if y < height - 1 and footsteps[y + 1][x] is None:
                queue.append(((x, y + 1), s + 1))
                footsteps[y + 1][x] = -1

        return s

    height, width = tuple(input_ints())
    # field = [input() for _ in range(height)]
    queue = deque()

    # for y, line in enumerate(field):
    #     for x, c in enumerate(line):
    #         if c == '#':
    #             queue.append(((x, y), 0))
    queue.append(((10, 10), 0))

    return fill(queue)


def main():
    print(solve())


main()

Submission status: Runtime Error

Solution code:
import numpy as np

h, w = map(int, input().split())
b = [[0] * w for _ in range(h)]
q = []

for i in range(h):
    for j, m in enumerate(input()):
        if m == "#":
            q.append((i, j))
            b[i][j] = 1

cnt = -1

while q:
    nq = []
    for y, x in q:
        if y > 0:
            if not b[y-1][x]:
                b[y-1][x] = 1
                nq.append((y-1, x))
        if y < h-1:
            if not b[y+1][x]:
                b[y+1][x] = 1
                nq.append((y+1, x))
        if x > 0:
            if not b[y][x-1]: 
                b[y][x-1] = 1
                nq.append((y, x-1))
        if x < w-1:
            if not b[y][x+1]: 
                b[y][x+1] = 1
                nq.append((y, x+1))
    
    q = nq    
    cnt += 1
    
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

h, w = map(int, input().split())
b = [[0] * w for _ in range(h)]
iq = []

for i in range(h):
    for j, m in enumerate(input()):
        if m == "#":
            iq.append((i, j))
            b[i][j] = 1

def bfs(q, cnt):
    nq = []
    for y, x in q:
        if y > 0:
            if not b[y-1][x]:
                b[y-1][x] = 1
                nq.append((y-1, x))
        if y < h-1:
            if not b[y+1][x]:
                b[y+1][x] = 1
                nq.append((y+1, x))
        if x > 0:
            if not b[y][x-1]: 
                b[y][x-1] = 1
                nq.append((y, x-1))
        if x < w-1:
            if not b[y][x+1]: 
                b[y][x+1] = 1
                nq.append((y, x+1))
                
    if nq: return bfs(nq, cnt + 1)
    return cnt
    
print(bfs(iq, 0))

Submission status: Runtime Error

Solution code:
from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


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


while q:
  cur=q.popleft()

  if 0<=cur[0]+1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]+1][cur[1]]==-1:
      lis[cur[0]+1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]+1,cur[1]))
  
  if 0<=cur[0]-1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]-1][cur[1]]==-1:
      lis[cur[0]-1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]-1,cur[1]))

  
  if 0<=cur[0]<=h-1 and 0<=cur[1]+1<=w-1:
    if lis[cur[0]][cur[1]+1]==-1:
      lis[cur[0]][cur[1]+1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]+1))
      
  if 0<=cur[0]<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[cur[0]][cur[1]-1]==-1:
      lis[cur[0]][cur[1]-1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]-1))      
  
print(max(max(l) for l in lis))