Problem p03053 (python)

Fixed submission:

import numpy as np

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

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

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

  # visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  visited = np.zeros((H, W), int)
  for y in range(H):
    # visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

  for y in range(1, H):  # ↓
    # 要素ごとの処理
    # print(visited)
    visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)
    # print(visited)
    # input()
    # print(visited[y])
    # exit(0)

  for y in range(H - 2, -1, -1):
    visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  for x in range(1, W):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  for x in range(W - 2, -1, -1):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(visited)
  # exit(0)

  # max_len = 0
  # for y in range(H):
  #   max_val = max(visited[y])
  #   max_len = max_len if max_len > max_val else max_val
  # print(max_len)
  print(np.max(visited))

if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):

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

Buggy submission (verdict: Runtime Error):

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

Buggy submission (verdict: Runtime Error):

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

Buggy submission (verdict: Runtime Error):

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

Buggy submission (verdict: Runtime Error):

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

Buggy submission (verdict: Runtime Error):

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

Buggy submission (verdict: Runtime Error):

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