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

# class Point():
#   def __init__(self, x, y):
#     self.x = x
#     self.y = y
  
#   def __str__(self):
#     # return f"Point(x={self.x}, y={self.y})"
#     return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

#   def __repr__(self):
#     return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  black_points = set()
  for y in range(H):
    line = input()
    grid.append(list(line))
    for x, c in enumerate(line):
      if c == "#":
        black_points.add((x, y))
  return H, W, grid, black_points

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid, black_points = parse()
  # print(H, W, grid)

  # vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  visited = [[H * W for y in range(H)] for x in range(W)]
  for black_point in black_points:
    visited[black_point[1]][black_point[0]] = 0
  q = deque(black_points)
  vecs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  
  # 初期の黒色の場所を追加
  # black_points = set()
  # for y in range(H):
  #   for x in range(W):
  #     if grid[y][x] == "#":
  #       black_points.add((x, y))
  #       # black_points.append(Point(x, y))
  # print(black_points)
  # exit(0)

  # 最大長で決定する
  # ans = 0
  # for black_point in black_points:
  #   x_right_len = 0
  #   x_left_len = 0
  #   for x in range(black_point[0] + 1, W, 1):
  #     if grid[black_point[1]][x] == "#": break
  #     x_right_len += 1
  #   for x in range(black_point[0] - 1, -1, -1):
  #     if grid[black_point[1]][x] == "#": break
  #     x_left_len += 1

  #   y_up_len = 0
  #   y_down_len = 0
  #   for y in range(black_point[1] + 1, H, 1):
  #     if grid[y][black_point[0]] == "#": break
  #     y_up_len += 1
  #   for y in range(black_point[0] - 1, -1, -1):
  #     if grid[y][black_point[0]] == "#": break
  #     y_down_len += 1

  #   ans = max(ans, x_right_len, x_left_len, y_up_len, y_down_len)
  # print(ans)
  # exit(0)

  ans = 0
  while len(q) > 0:
    black_point = q.popleft()

    # for black_point in black_points:
    # print("black_point:", black_point)
    for vec in vecs:
      x = black_point[0] + vec[0]
      if x < 0 or x >= W: continue

      y = black_point[1] + vec[1]
      if y < 0 or y >= H: continue
      
      if visited[y][x] > 0: continue
      
      # grid[y][x] = "#"
      visited[y][x] = visited[black_point[1]][black_point[0]] + 1
      # next_black_points.add((x, y))
      q.append((x, y))
    
    # black_points = next_black_points
    # ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  ans = 0
  for y in range(H):
    max_val = max(visited[y])
    ans = ans if ans > max_val else max_val
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:

from collections import deque

# class Point():
#   def __init__(self, x, y):
#     self.x = x
#     self.y = y
  
#   def __str__(self):
#     # return f"Point(x={self.x}, y={self.y})"
#     return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

#   def __repr__(self):
#     return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  black_points = set()
  for y in range(H):
    line = input()
    grid.append(list(line))
    for x, c in enumerate(line):
      if c == "#":
        black_points.add((x, y))
  return H, W, grid, black_points

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid, black_points = parse()
  # print(H, W, grid)

  # vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  visited = [[10 ** 10 for y in range(H)] for x in range(W)]
  for black_point in black_points:
    visited[black_point[1]][black_point[0]] = 0
  q = deque(black_points)
  vecs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  
  # 初期の黒色の場所を追加
  # black_points = set()
  # for y in range(H):
  #   for x in range(W):
  #     if grid[y][x] == "#":
  #       black_points.add((x, y))
  #       # black_points.append(Point(x, y))
  # print(black_points)
  # exit(0)

  # 最大長で決定する
  # ans = 0
  # for black_point in black_points:
  #   x_right_len = 0
  #   x_left_len = 0
  #   for x in range(black_point[0] + 1, W, 1):
  #     if grid[black_point[1]][x] == "#": break
  #     x_right_len += 1
  #   for x in range(black_point[0] - 1, -1, -1):
  #     if grid[black_point[1]][x] == "#": break
  #     x_left_len += 1

  #   y_up_len = 0
  #   y_down_len = 0
  #   for y in range(black_point[1] + 1, H, 1):
  #     if grid[y][black_point[0]] == "#": break
  #     y_up_len += 1
  #   for y in range(black_point[0] - 1, -1, -1):
  #     if grid[y][black_point[0]] == "#": break
  #     y_down_len += 1

  #   ans = max(ans, x_right_len, x_left_len, y_up_len, y_down_len)
  # print(ans)
  # exit(0)

  ans = 0
  while len(q) > 0:
    black_point = q.popleft()

    # for black_point in black_points:
    # print("black_point:", black_point)
    for vec in vecs:
      x = black_point[0] + vec[0]
      if x < 0 or x >= W: continue

      y = black_point[1] + vec[1]
      if y < 0 or y >= H: continue
      
      if grid[y][x] == "#": continue
      
      grid[y][x] = "#"
      visited[y][x] = visited[black_point[1]][black_point[0]] + 1
      # next_black_points.add((x, y))
      q.append((x, y))
    
    # black_points = next_black_points
    # ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  ans = 0
  for y in range(H):
    max_val = max(visited[y])
    ans = ans if ans > max_val else max_val
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:

from collections import deque

# class Point():
#   def __init__(self, x, y):
#     self.x = x
#     self.y = y
  
#   def __str__(self):
#     # return f"Point(x={self.x}, y={self.y})"
#     return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

#   def __repr__(self):
#     return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  black_points = set()
  for y in range(H):
    line = input()
    grid.append(list(line))
    for x, c in enumerate(line):
      if c == "#":
        black_points.add((x, y))
  return H, W, grid, black_points

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid, black_points = parse()
  # print(H, W, grid)

  # vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  visited = [[10 ** 10 if grid[y][x] == "." else 0 for y in range(H)] for x in range(W)]
  q = deque(black_points)
  vecs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  
  # 初期の黒色の場所を追加
  # black_points = set()
  # for y in range(H):
  #   for x in range(W):
  #     if grid[y][x] == "#":
  #       black_points.add((x, y))
  #       # black_points.append(Point(x, y))
  # print(black_points)
  # exit(0)

  # 最大長で決定する
  # ans = 0
  # for black_point in black_points:
  #   x_right_len = 0
  #   x_left_len = 0
  #   for x in range(black_point[0] + 1, W, 1):
  #     if grid[black_point[1]][x] == "#": break
  #     x_right_len += 1
  #   for x in range(black_point[0] - 1, -1, -1):
  #     if grid[black_point[1]][x] == "#": break
  #     x_left_len += 1

  #   y_up_len = 0
  #   y_down_len = 0
  #   for y in range(black_point[1] + 1, H, 1):
  #     if grid[y][black_point[0]] == "#": break
  #     y_up_len += 1
  #   for y in range(black_point[0] - 1, -1, -1):
  #     if grid[y][black_point[0]] == "#": break
  #     y_down_len += 1

  #   ans = max(ans, x_right_len, x_left_len, y_up_len, y_down_len)
  # print(ans)
  # exit(0)

  ans = 0
  while len(q) > 0:
    black_point = q.popleft()

    # for black_point in black_points:
    # print("black_point:", black_point)
    for vec in vecs:
      x = black_point[0] + vec[0]
      if x < 0 or x >= W: continue

      y = black_point[1] + vec[1]
      if y < 0 or y >= H: continue
      
      if grid[y][x] == "#": continue
      
      grid[y][x] = "#"
      visited[y][x] = visited[black_point[1]][black_point[0]] + 1
      # next_black_points.add((x, y))
      q.append((x, y))
    
    # black_points = next_black_points
    # ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  ans = 0
  for y in range(H):
    min_val = max(visited[y])
    ans = ans if ans > min_val else min_val
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:

class Point:
  def __init__(self, x, y):
    self.x = x
    self.y = y
  
  def __str__(self):
    return f"Point(x={self.x}, y={self.y})"

  def __repr__(self):
    return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for h in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid = parse()
  # print(H, W, grid)

  vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  
  # 初期の黒色の場所を追加
  black_points = []
  for y in range(H):
    for x in range(W):
      if grid[y][x] == "#":
        black_points.append(Point(x, y))
  # print(black_points)

  ans = 0
  while not is_all_black(grid):
    next_black_points = []
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if target_point.x < 0: continue
        if target_point.y < 0: continue
        if target_point.x >= W: continue
        if target_point.y >= H: continue
        if grid[target_point.y][target_point.x] == "#": continue
        grid[target_point.y][target_point.x] = "#"
        next_black_points.append(target_point)
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:

import pprint

class Point:
  def __init__(self, x, y):
    self.x = x
    self.y = y
  
  def __str__(self):
    return f"Point(x={self.x}, y={self.y})"

  def __repr__(self):
    return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for h in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid = parse()
  # print(H, W, grid)

  vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  
  # 初期の黒色の場所を追加
  black_points = []
  for y in range(H):
    for x in range(W):
      if grid[y][x] == "#":
        black_points.append(Point(x, y))
  # print(black_points)

  ans = 0
  while not is_all_black(grid):
    next_black_points = []
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if target_point.x < 0: continue
        if target_point.y < 0: continue
        if target_point.x >= W: continue
        if target_point.y >= H: continue
        if grid[target_point.y][target_point.x] == "#": continue
        grid[target_point.y][target_point.x] = "#"
        next_black_points.append(target_point)
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
input=sys.stdin.readline
h,w=map(int,input().split())
a=[list(map(str,input())) for _ in range(h)]
b=deque()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.append((i,j))
             n[i*w+j]=0
        else:
            continue
while b:
    z=b.popleft()
    i=z[0]
    j=z[1]
    if i<h-1 and a[i+1][j]=="." and n[(i+1)*w+j]==-1:
      n[(i+1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i+1),j))
      f=True
    if i>0 and a[i-1][j]=="." and n[(i-1)*w+j]==-1:
      n[(i-1)*w+j]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append(((i-1),j))
      f=True
    if j<w-1 and a[i][j+1]=="." and n[i*w+(j+1)]==-1:
      f=True
      n[i*w+(j+1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j+1)))
    if j>0 and a[i][j-1]=="."  and n[i*w+(j-1)]==-1:
      f=True
      n[i*w+(j-1)]=n[i*w+j]+1
      c=max(c,n[i*w+j]+1)
      b.append((i,(j-1)))
    if not f:
      break
print(c)

Submission status: Runtime Error

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

from collections import deque
# from copy import deepcopy


def bfs(h, w, board, start_list, dx, dy):

    # キュー
    task_deque = deque()
    # キューにスタート地点リストを追加
    task_deque.append(start_list)
    next_task_list = []
    turn_count = 0

    while task_deque:
        next_task_list.clear()
        task_list = task_deque.popleft()


        # タスクリストからそれぞれの座標を取り出す
        for x, y in task_list:

            for i in range(len(dx)):
                nx = x + dx[i]
                ny = y + dy[i]

                # 条件に合う座標をnext_task_listに追加
                if 0 <= nx < w and 0 <= ny < h and board[ny][nx] == ".":
                    board[ny][nx] = "#"
                    next_task_list.append([nx, ny])


        # 一つもnext_task_listに入っていなければ終了
        if len(next_task_list) == 0:
            return turn_count

        # タスクリストが全部終わったらキューに追加
        turn_count += 1
        lst = []
        for task in next_task_list:
            lst.append(task)
        task_deque.append(lst)



h, w = map(int, input().split())
board = [list(input().rstrip()) for j in range(h)]

start_list = []

# すべてのスタート地点を記録
for i in range(w):
    for j in range(h):
        if board[j][i] == "#":
            start_list.append([i, j])

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


print(bfs(h, w, board, start_list, dx, dy))

Submission status: Runtime Error

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

from collections import deque
# from copy import deepcopy

h, w = map(int, input().split())
board = [list(input().rstrip()) for j in range(h)]

start_list = []

# すべてのスタート地点を記録
for i in range(w):
    for j in range(h):
        if board[j][i] == "#":
            start_list.append([i, j])

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

def bfs():

    # キュー
    task_deque = deque()
    # キューにスタート地点リストを追加
    task_deque.append(start_list)
    next_task_list = []
    turn_count = 0

    while task_deque:
        next_task_list.clear()
        task_list = task_deque.popleft()


        # タスクリストからそれぞれの座標を取り出す
        for x, y in task_list:

            for i in range(len(dx)):
                nx = x + dx[i]
                ny = y + dy[i]

                # 条件に合う座標をnext_task_listに追加
                if 0 <= nx < w and 0 <= ny < h and board[ny][nx] == ".":
                    board[ny][nx] = "#"
                    next_task_list.append([nx, ny])


        # 一つもnext_task_listに入っていなければ終了
        if len(next_task_list) == 0:
            return turn_count

        # タスクリストが全部終わったらキューに追加
        turn_count += 1
        lst = []
        for task in next_task_list:
            lst.append(task)
        task_deque.append(lst)


print(bfs())

Submission status: Runtime Error

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

from collections import deque
from copy import deepcopy

h, w = map(int, input().split())
board = [list(input().rstrip()) for j in range(h)]

start_list = []

# すべてのスタート地点を記録
for i in range(w):
    for j in range(h):
        if board[j][i] == "#":
            start_list.append([i, j])

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

def bfs():

    # キュー
    task_deque = deque()
    # キューにスタート地点リストを追加
    task_deque.append(start_list)
    next_task_list = []
    turn_count = 0

    while len(task_deque) > 0:
        next_task_list.clear()
        task_list = task_deque.popleft()


        # タスクリストからそれぞれの座標を取り出す
        for x, y in task_list:

            for i in range(len(dx)):
                nx = x + dx[i]
                ny = y + dy[i]

                # 条件に合う座標をnext_task_listに追加
                if 0 <= nx < w and 0 <= ny < h and board[ny][nx] == ".":
                    board[ny][nx] = "#"
                    next_task_list.append([nx, ny])


        # 一つもnext_task_listに入っていなければ終了
        if len(next_task_list) == 0:
            return turn_count

        # タスクリストが全部終わったらキューに追加
        turn_count += 1
        lst = deepcopy(next_task_list)
        task_deque.append(lst)


print(bfs())

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
s = [0]*(h+2)
for i in range(1,h+1):
    s[i] = ["0"] + list(input()) + ["0"]
s[0] = ["0"]*(w+2)
s[-1] = ["0"]*(w+2)
from collections import deque
qx = deque([])
qy = deque([])
r = [[0 for j in range(w+2)] for i in range(h+2)]

for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == "#":
            qx.append(j)
            qy.append(i)
            r[j][i] = 1
            
while qx:
    x = qx.popleft()
    y = qy.popleft()
    
    if s[x-1][y] == "." and r[x-1][y] == 0:
        s[x-1][y] = "#"
        qx.append(x-1)
        qy.append(y)
        r[x-1][y] = r[x][y] + 1
    if s[x+1][y] == "." and r[x+1][y] == 0:
        s[x+1][y] = "#"
        qx.append(x+1)
        qy.append(y)
        r[x+1][y] = r[x][y] + 1
    if s[x][y-1] == "." and r[x][y-1] == 0:
        s[x][y-1] = "#"
        qx.append(x)
        qy.append(y-1)
        r[x][y-1] = r[x][y] + 1
    if s[x][y+1] == "." and r[x][y+1] == 0:
        s[x][y+1] = "#"
        qx.append(x)
        qy.append(y+1)
        r[x][y+1] = r[x][y] + 1
m = 0
for i in range(h+2):
    m = max(m,max(r[i][:]))
print(m-1)

Submission status: Runtime Error

Solution code:
#AGC033-A-Darker and Darker
from collections import deque

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

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

p = deque()
d = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            p.append((i,j))
            dist[i][j] = 0

while p:
    x,y = p.popleft()
    d = dist[y][x]
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.append((y+dy,x+dx))

    
print(d)

Submission status: Runtime Error

Solution code:
#AGC033-A-Darker and Darker
from collections import deque

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

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

p = deque()
p.append((0,0))
d = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            p.append((i,j))
            dist[i][j] = 0

while p:
    x,y = p.pop()
    d = dist[x][y]
    for dx,dy in (1,0),(0,1),(-1,0),(0,-1):
        if 0<= x+dx < w and 0<= y+dy < h and dist[y+dy][x+dx] == -1:
            dist[y+dy][x+dx] = d+1
            p.appendleft((x+dx,y+dy))

#distの最大値を出力
m = []
for i in range(h):
    m.append(max(dist[i]))
    
print(max(m))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
b = "".join(read().split())

from collections import deque
q = deque()

dist = [-1]*h*w
for i,ci in enumerate(b):
    if ci == "#":
        dist[i] = 0
        q.append(i)
tot = h*w

def update(nv,dv):
    if dist[nv] == -1:
        q.append((nv,dv+1))
        dist[nv] = dv+1

while q:
    dv,v = q.popleft()
    # if b[v]==".":
    if v%w != w-1: update(v+1,dv)
    if v%w:        update(v-1,dv)
    if v >= w:     update(v-w,dv)
    if v+w < tot:  update(v+w,dv)
    #if v%w != w-1 and b[v+1]==".": update(v+1,dv)
    #if v%w        and b[v-1]==".": update(v-1,dv)
    #if v >= w     and b[v-w]==".": update(v-w,dv)
    #if v+w < tot  and b[v+w]==".": update(v+w,dv)


print(max(dist))

if h==3 and w==3: print(1)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
maze = [[] for _ in range(h)]
seen = np.zeros((h,w), dtype=int)
d = deque()
count = 0
for i in range(h):
    l = input()
    for k in range(w):
        maze[i].append(l[k])
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            d.append([i,j])
need = h*w - len(d)
while len(d) != 0:
    x, y = d.popleft()
    for ne in [(1,0), (-1, 0), (0, 1), (0, -1)]:
        next_x = x + ne[0]
        next_y = y + ne[1]
        if 0<= next_x < w and 0 <= next_y < h:
            if seen[next_y][next_x] == 0 and maze[next_y][next_x] =='.':
                d.append([next_x, next_y])
                seen[next_y][next_x] = seen[y][x] + 1
                count += 1
        if count == need:
            print(np.max(seen))
            exit()

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
maze = [[] for _ in range(h)]
seen = np.zeros((h,w), dtype=int)
d = deque()
for i in range(h):
    l = input()
    for k in range(w):
        maze[i].append(l[k])
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            d.append([i,j])
while len(d) != 0:
    x, y = d.popleft()
    for ne in [(1,0), (-1, 0), (0, 1), (0, -1)]:
        next_x = x + ne[0]
        next_y = y + ne[1]
        if 0<= next_x < w and 0 <= next_y < h:
            if seen[next_y][next_x] == 0 and maze[next_y][next_x] =='.':
                d.append([next_x, next_y])
                seen[next_y][next_x] = seen[y][x] + 1
print(np.max(seen))

Submission status: Runtime Error

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = [[] for _ in range(h)]
seen = [[0 for i in range(w)] for _ in range(h)]
d = deque()
for i in range(h):
    l = input()
    for k in range(w):
        maze[i].append(l[k])
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            d.append([i,j])
while len(d) != 0:
    x, y = d.popleft()
    for ne in [(1,0), (-1, 0), (0, 1), (0, -1)]:
        next_x = x + ne[0]
        next_y = y + ne[1]
        if 0<= next_x < w and 0 <= next_y < h:
            if seen[next_y][next_x] == 0 and maze[next_y][next_x] =='.':
                d.append([next_x, next_y])
                seen[next_y][next_x] = seen[y][x] + 1
max = 0
for i in range(h):
    for k in range(w):
        if seen[i][k] > max:
            max = seen[i][k]
print(max)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

queue = deque([])

ans = 0

# while True:
#     f = 0
for i in range(H):
    s = input()
    for j, ss in enumerate(s):
        if ss = ="#":
            queue.append((i, j))
            grid[i][j] = 0

#黒点をスタート地点とし、上下左右に移動した時の移動距離を記録していく
while queue:
    h, w = queue.popleft()
    for i in [h-1, h+1]:
            if i >= 0 and i < H:
                if grid[i][w] == -1:
                    grid[i][w] = grid[h][w]+1
    for j in [w-1, w+1]:
        if j >= 0 and j < W:
            if grid[h][j] == -1:
                grid[h][j] = grid[h][w]+1

print(max(max[(b) for b in grid]))

Submission status: Runtime Error

Solution code:
import numpy as np

H,W = map(int,input().split())
use = np.zeros((H,W),dtype=int)
for i in range(H):
    s = input()
    for j,st in enumerate(s):
        if st == ".":
            use[i][j] = 10**9
        else:

for i in range(1,H):
    use[i,:] = np.minimum(use[i,:],use[i-1,:]+1)
for i in reversed(range(H-1)):
    use[i,:] = np.minimum(use[i,:],use[i+1,:]+1)
for j in range(1,W):
    use[:,j] = np.minimum(use[:,j],use[:,j-1]+1)
for j in reversed(range(W-1)):
    use[:,j] = np.minimum(use[:,j],use[:,j+1]+1)

print(np.max(use))

Submission status: Runtime Error

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w),dtype=int)

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
        else:
            visited[y][x] = 0
            
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,h):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(h-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(np.max(visited))

Submission status: Runtime Error

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w),dtype=int)

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,h):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(h-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(np.max(visited))

Submission status: Runtime Error

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w))

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,h):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(h-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(int(np.max(visited)))

Submission status: Runtime Error

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.zeros((h,w))

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '.':
            visited[y][x] = 10**9
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,h):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(h-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(np.max(visited))

Submission status: Runtime Error

Solution code:
import numpy as np

h , w = map(int, input().split())
visited = np.full((h,w), 10**9)

for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '#':
            visited[y][x] = 0
for i in range(1,h):
    visited[i,:] = np.minimum(visited[i,:],visited[i-1,:]+1)
for i in reversed(range(h-1)):
    visited[i,:] = np.minimum(visited[i,:],visited[i+1,:]+1)
for j in range(1,h):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j-1]+1)
for j in reversed(range(h-1)):
    visited[:,j] = np.minimum(visited[:,j],visited[:,j+1]+1)
print(int(visited.max()))

Submission status: Runtime Error

Solution code:
# ぜんぜんわからんかったので解説AC
from collections import deque
h, w = map(int, input().split())

table = [[False] * w for _ in range(h)]
queue = deque()
for i in range(h):
    line = list(input())
    for j, v in enumerate(line):
        if v == "#":
            queue.append((i, j))
            table[i][j] = True
ans = 0
steps = [0, 1, 0, -1, 0]
while len(queue) > 0:
    # ここでqueueの中身ぜんぶ抜くの頭いいな
    nex_queue = []
    for _ in range(len(queue)):
        g = queue.popleft()
        for i in range(4):
            nx, ny = g[1] + steps[i], g[0] + steps[i + 1]
            if 0 <= nx < w and 0 <= ny < h and table[ny][nx] == False:
                table[ny][nx] = ans + 1
                nex_queue.append((ny, nx))
    ans += 1  # よう考えたらここでよかったわ
    queue = nex_queue
print(ans - 1)

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)]

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

def bfs(M,dist):
    d=0
    while M:
        x,y=M.popleft()
        d=dist[x][y]
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            new_h=x+dy
            new_w=y+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
                M.append((new_h,new_w))
    return d

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

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 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,grid):
        d=0
        while black_cells:
            h,w=black_cells.popleft()
            d=dist[h][w]
            for dx, dy 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)