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: Time Limit Exceeded

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked += [[True]*(W+2)]

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from collections import deque

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)

  dark_points = [(x + 1, y + 1) for x in range(W) for y in range(H) if grid[y][x] == "#"]

  visited = [[True if x == 0 or y == 0 or x == W + 1 or y == H + 1 else False for x in range(W + 2)] for y in range(H + 2)]
  for x, y in dark_points:
    visited[y][x] = True
  # for y in range(H + 2):
  #   print(visited[y])
  # exit(0)

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

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

  # 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(dark_points)
  # exit(0)

  q = dark_points
  ans = 0
  while len(q) > 0:
    ans += 1
    next_q = []
    for x, y in q:
      if not visited[y - 1][x]: # 上
        visited[y - 1][x] = ans
        next_q.append((x, y - 1))
      if not visited[y + 1][x]: # 下
        visited[y + 1][x] = ans
        next_q.append((x, y + 1))
      if not visited[y][x - 1]: # 左
        visited[y][x - 1] = ans
        next_q.append((x - 1, y))
      if not visited[y][x + 1]: # 右
        visited[y][x + 1] = ans
        next_q.append((x + 1, y))
      
    # for y in range(H + 2):
    #   print(visited[y])
    # input()
    
    q = next_q

  print(ans - 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [False]*W + [True] for i in range(H)]
checked += [[True]*(W+2)]
black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i+1][j+1] = True
            black_list.append((i+1, j+1))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from collections import deque

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)

  dark_points = [(x + 1, y + 1) for x in range(W) for y in range(H) if grid[y][x] == "#"]

  visited = [[0 if x == 0 or y == 0 or x == W + 1 or y == H + 1 else -1 for x in range(W + 2)] for y in range(H + 2)]
  for x, y in dark_points:
    visited[y][x] = 0
  # for y in range(H + 2):
  #   print(visited[y])
  # exit(0)

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

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

  # 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(dark_points)
  # exit(0)

  q = dark_points
  ans = 0
  while len(q) > 0:
    ans += 1
    next_q = []
    for x, y in q:
      if visited[y - 1][x] == -1: # 上
        visited[y - 1][x] = ans
        next_q.append((x, y - 1))
      if visited[y + 1][x] == -1: # 下
        visited[y + 1][x] = ans
        next_q.append((x, y + 1))
      if visited[y][x - 1] == -1: # 左
        visited[y][x - 1] = ans
        next_q.append((x - 1, y))
      if visited[y][x + 1] == -1: # 右
        visited[y][x + 1] = ans
        next_q.append((x + 1, y))
      
    # for y in range(H + 2):
    #   print(visited[y])
    # input()
    
    q = next_q

  print(ans - 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from collections import deque

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)

  dark_points = [(x + 1, y + 1) for x in range(W) for y in range(H) if grid[y][x] == "#"]

  visited = [[0 if x == 0 or y == 0 or x == W + 1 or y == H + 1 else -1 for x in range(W + 2)] for y in range(H + 2)]
  for x, y in dark_points:
    visited[y][x] = 0
  # for y in range(H + 2):
  #   print(visited[y])
  # exit(0)

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

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

  # 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(dark_points)
  # exit(0)

  q = deque(dark_points)
  ans = 0
  while len(q) > 0:
    ans += 1
    next_q = deque([])
    for x, y in q:
      if visited[y - 1][x] == -1: # 上
        visited[y - 1][x] = ans
        next_q.append((x, y - 1))
      if visited[y + 1][x] == -1: # 下
        visited[y + 1][x] = ans
        next_q.append((x, y + 1))
      if visited[y][x - 1] == -1: # 左
        visited[y][x - 1] = ans
        next_q.append((x - 1, y))
      if visited[y][x + 1] == -1: # 右
        visited[y][x + 1] = ans
        next_q.append((x + 1, y))
      
    # for y in range(H + 2):
    #   print(visited[y])
    # input()
    
    q = next_q

  print(ans - 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [-1]*W + [True] for i in range(H)]
checked += [[True]*(W+2)]

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i+1][j+1] = True
            black_list.append((i+1, j+1))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while len(black_list) > 0:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if checked[x-1][y] == -1:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if checked[x+1][y] == -1:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if checked[x][y-1] == -1:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if checked[x][y+1] == -1:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from collections import deque

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 = [[0 for x in range(W)] for y in range(H)]
  # visited = np.zeros((H, W), int)
  # for y in range(H):
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y][x] = H * W

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

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

  dark_points = [(x, y) for x in range(W) for y in range(H) if grid[y][x] == "#"]
  # print(dark_points)
  # exit(0)

  q = deque(dark_points)
  ans = 0
  while len(q) > 0:
    ans += 1
    next_q = deque([])
    for x, y in q:
      if y - 1 >= 0 and not visited[y - 1][x]: # 上
        visited[y - 1][x] = ans
        next_q.append((x, y - 1))
      if y + 1 < H and not visited[y + 1][x]: # 下
        visited[y + 1][x] = ans
        next_q.append((x, y + 1))
      if x - 1 >= 0 and not visited[y][x - 1]: # 左
        visited[y][x - 1] = ans
        next_q.append((x - 1, y))
      if x + 1 < W and not visited[y][x + 1]: # 右
        visited[y][x + 1] = ans
        next_q.append((x + 1, y))
    q = next_q

  print(ans - 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]
black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            black_list.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while black_list:
    queue = deque(black_list)
    black_list = []
    while queue:
        x, y = queue.popleft()

        # 周囲探索
        for dx, dy in directions:
            xx = x + dx
            yy = y + dy

            if xx >= 0 and xx < H and yy >= 0 and yy < W:
                if checked[xx][yy] == -1:
                    checked[xx][yy] = checked[x][y] + 1
                    black_list.append((xx, yy))

        # # 上
        # if x-1 > -1 and checked[x-1][y] == -1:
        #     checked[x-1][y] = checked[x][y] + 1
        #     black_list.append((x-1, y))
        # # 下
        # if x+1 < H and checked[x+1][y] == -1:
        #     checked[x+1][y] = checked[x][y] + 1
        #     black_list.append((x+1, y))
        # # 左
        # if y-1 > -1 and checked[x][y-1] == -1:
        #     checked[x][y-1] = checked[x][y-1] + 1
        #     black_list.append((x, y-1))

        # # 右
        # if y+1 < W and checked[x][y+1] == -1:
        #     checked[x][y+1] = checked[x][y+1] + 1
        #     black_list.append((x, y+1))


ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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)]
  # for y in range(H):
  #   visited.append([])
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y].append(H * W)
  #     else:
  #       visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x_right, x_left in zip(range(1, W), range(W - 2, -1, -1)):  # →，←
      # →
      visited_left = visited[y][x_right - 1] + 1
      visited[y][x_right] = visited_left if visited_left < visited[y][x_right] else visited[y][x_right]
      
      # ←
      visited_right = visited[y][x_left + 1] + 1
      visited[y][x_left] = visited[y][x_left] if visited[y][x_left] < visited_right else visited_right

  for x in range(W):  # →
    for y_down, y_up in zip(range(1, H), range(H - 2, -1, -1)):  # ↓，↑
      # ↓
      visited_up = visited[y_down - 1][x] + 1
      visited[y_down][x] = visited_up if visited_up < visited[y_down][x] else visited[y_down][x]
      
      # ↑
      visited_down = visited[y_up + 1][x] + 1
      visited[y_up][x] = visited[y_up][x] if visited[y_up][x] < visited_down else visited_down
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

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)]
  # for y in range(H):
  #   visited.append([])
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y].append(H * W)
  #     else:
  #       visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x_right, x_left in zip(range(1, W), range(W - 2, -1, -1)):  # →，←
      visited[y][x_right] = visited[y][x_right - 1] + 1 if visited[y][x_right - 1] + 1 < visited[y][x_right] else visited[y][x_right]
      visited[y][x_left] = visited[y][x_left] if visited[y][x_left] < visited[y][x_left + 1] + 1 else visited[y][x_left + 1] + 1

  for x in range(W):  # →
    for y_down, y_up in zip(range(1, H), range(H - 2, -1, -1)):  # ↓，↑
      visited[y_down][x] = min(visited[y_down - 1][x] + 1, visited[y_down][x])
      visited[y_up][x] = min(visited[y_up][x], visited[y_up + 1][x] + 1)
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        xx = x + dx
        yy = y + dy

        if xx >= 0 and xx < H and yy >= 0 and yy < W:
            if checked[xx][yy] == -1:
                checked[xx][yy] = checked[x][y] + 1
                queue.append((xx, yy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for y in range(H):
    grid.append(list(input()))
  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)]
  # for y in range(H):
  #   visited.append([])
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y].append(H * W)
  #     else:
  #       visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x_right, x_left in zip(range(1, W), range(W - 2, -1, -1)):  # →，←
      visited[y][x_right] = min(visited[y][x_right - 1] + 1, visited[y][x_right])
      visited[y][x_left] = min(visited[y][x_left], visited[y][x_left + 1] + 1)

  for x in range(W):  # →
    for y_down, y_up in zip(range(1, H), range(H - 2, -1, -1)):  # ↓，↑
      visited[y_down][x] = min(visited[y_down - 1][x] + 1, visited[y_down][x])
      visited[y_up][x] = min(visited[y_up][x], visited[y_up + 1][x] + 1)
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        xx = x + dx
        yy = y + dy
        if xx < 0 or xx >= H:
            continue

        if yy < 0 or yy >= W:
            continue

        if checked[xx][yy] == -1:
            checked[xx][yy] = checked[x][y] + 1
            queue.append((xx, yy))

# ans = 0
# for i in range(H):
#     for j in range(W):
#         if ans < checked[i][j]:
#             ans = checked[i][j]

print(np.max(checked))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        xx = x + dx
        yy = y + dy
        if xx < 0 or xx >= H:
            continue

        if yy < 0 or yy >= W:
            continue

        if checked[xx][yy] == -1:
            checked[xx][yy] = checked[x][y] + 1
            queue.append((xx, yy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]

print(np.max(checked))

Submission status: Time Limit Exceeded

Solution code:

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for y in range(H):
    grid.append(list(input()))
  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)]
  # for y in range(H):
  #   visited.append([])
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y].append(H * W)
  #     else:
  #       visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x in range(1, W):  # →
      visited[y][x] = min(visited[y][x - 1] + 1, visited[y][x])
    for x in range(W - 2, -1, -1):  # ←
      visited[y][x] = min(visited[y][x], visited[y][x + 1] + 1)

  # for y in range(H):  # ↓
  #   for x in range(1, W):  # →
  #     visited[y][x] = min(visited[y][x - 1] + 1, visited[y][x])
  # for y in range(H):  # ↓
  #   for x in range(W - 2, -1, -1):  # ←
  #     visited[y][x] = min(visited[y][x], visited[y][x + 1] + 1)
  
  for x in range(W):  # →
    for y in range(1, H):  # ↓
      visited[y][x] = min(visited[y - 1][x] + 1, visited[y][x])
    for y in range(H - 2, -1, -1):  # ↑
      visited[y][x] = min(visited[y][x], visited[y + 1][x] + 1)

  # for x in range(W):  # →
  #   for y in range(1, H):  # ↓
  #     visited[y][x] = min(visited[y - 1][x] + 1, visited[y][x])
  # for x in range(W):  # →
  #   for y in range(H - 2, -1, -1):  # ↑
  #     visited[y][x] = min(visited[y][x], visited[y + 1][x] + 1)
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        xx = x + dx
        yy = y + dy
        if xx < 0 or xx >= H:
            continue

        if yy < 0 or yy >= W:
            continue

        if checked[xx][yy] == -1:
            checked[xx][yy] = checked[x][y] + 1
            queue.append((xx, yy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for y in range(H):
    grid.append(list(input()))
  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)]
  # for y in range(H):
  #   visited.append([])
  #   for x in range(W):
  #     if grid[y][x] == ".":
  #       visited[y].append(H * W)
  #     else:
  #       visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x in range(1, W):  # →
      visited[y][x] = min(visited[y][x - 1] + 1, visited[y][x])
  for y in range(H):  # ↓
    for x in range(W - 2, -1, -1):  # ←
      visited[y][x] = min(visited[y][x], visited[y][x + 1] + 1)
  for x in range(W):  # →
    for y in range(1, H):  # ↓
      visited[y][x] = min(visited[y - 1][x] + 1, visited[y][x])
  for x in range(W):  # →
    for y in range(H - 2, -1, -1):  # ↑
      visited[y][x] = min(visited[y][x], visited[y + 1][x] + 1)
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]

queue = deque([])

# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            queue.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while queue:
    x, y = queue.popleft()

    # 周囲探索
    for dx, dy in directions:
        if x+dx < 0 or x+dx >= H:
            continue

        if y+dy < 0 or y+dy >= W:
            continue

        if checked[x+dx][y+dy] == -1:
            checked[x+dx][y+dy] = checked[x][y] + 1
            queue.append((x+dx, y+dy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for y in range(H):
    grid.append(list(input()))
  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 = []
  for y in range(H):
    visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y].append(H * W)
      else:
        visited[y].append(0)
    # print(visited[y])
  
  for y in range(H):  # ↓
    for x in range(1, W):  # →
      visited[y][x] = min(visited[y][x - 1] + 1, visited[y][x])
  for y in range(H):  # ↓
    for x in range(W - 2, -1, -1):  # ←
      visited[y][x] = min(visited[y][x], visited[y][x + 1] + 1)
  for x in range(W):  # →
    for y in range(1, H):  # ↓
      visited[y][x] = min(visited[y - 1][x] + 1, visited[y][x])
  for x in range(W):  # →
    for y in range(H - 2, -1, -1):  # ↑
      visited[y][x] = min(visited[y][x], visited[y + 1][x] + 1)
  
  max_len = 0
  for y in range(H):
    max_len = max_len if max_len > max(visited[y]) else max(visited[y])
  print(max_len)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# # 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
# #
# import deque
# H, W = map(int, input().rstrip().split())

# Map = []

# for i in range(H):
#     Map.append(list(input().rstrip()))

# black_list = []

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


# def search(black_list):
#     next_nodes = []
#     for pos in black_list:
#         x, y = pos

#         for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
#             dx, dy = direction

#             if x+dx < 0 or y+dy < 0:
#                 continue

#             if x+dx >= H or y+dy >= W:
#                 continue

#             if Map[x+dx][y+dy] == "#":
#                 continue

#             Map[x+dx][y+dy] = "#"
#             next_nodes.append((x+dx, y+dy))

#     return next_nodes


# count = 0
# while black_list:
#     black_list = search(black_list)
#     if len(black_list) > 0:
#         count += 1

# print(count)

from collections import deque
H, W = map(int, input().rstrip().split())

Map = []

for i in range(H):
    Map.append(list(input().rstrip()))

black_list = []

check = [[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        if Map[i][j] == "#":
            check[i][j] = 1
            black_list.append((i, j))

queue = deque(black_list)

while queue:
    pos = queue.popleft()
    x, y = pos

    # 各方向を確認する
    for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        dx, dy = direction

        if x+dx < 0:
            continue
        if x+dx >= H:
            continue
        if y+dy < 0:
            continue
        if y+dy >= W:
            continue

        # 白は黒に置き換える
        if check[x+dx][y+dy] == 0:
            check[x+dx][y+dy] = check[x][y] + 1
            queue.append((x+dx, y+dy))

ans = 0
for i in range(H):
    for j in range(W):
        if ans < check[i][j]:
            ans = check[i][j]

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

H,W = map(int,input().split())
q = []
visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 0

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = dp[h][w] + 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = dp[h][w] + 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = dp[h][w] + 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = dp[h][w] + 1
            temp.append([h,w-1])
    ls = temp

print(ans)