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:
from collections import deque

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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ls = deque([])
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

while len(ls) > 0:
    h, w = ls.popleft()

    if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
        dp[h+1][w] = dp[h][w] + 1
        ls.append([h+1,w])
    if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
        dp[h-1][w] = dp[h][w] + 1
        ls.append([h-1,w])
    if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
        dp[h][w+1] = dp[h][w] + 1
        ls.append([h,w+1])
    if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
        dp[h][w-1] = dp[h][w] + 1
        ls.append([h,w-1])

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
#
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)

Submission status: Time Limit Exceeded

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})"
#     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)]
  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
  while len(black_points) > 0:
  # while not is_all_black(grid):
    next_black_points = set()
    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] = "#"
        next_black_points.add((x, y))
    black_points = next_black_points
    ans += 1

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

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ls = deque([])
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

dir = [[1,0],[-1,0],[0,1],[0,-1]]
while len(ls) > 0:
    h, w = ls.popleft()

    for dx, dy in dir:
        if h + dx < 0 or H - 1 < h + dx: continue
        if w + dy < 0 or W - 1 < w + dy: continue
        if dp[h+dx][w+dy] == -1 and G[h+dx][w+dy] == ".":
            dp[h+dx][w+dy] = dp[h][w] + 1
            ls.append([h+dx,w+dy])

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])

print(ans)

Submission status: Time Limit Exceeded

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})"
#     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 = []
  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)]
  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))

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

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

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

  ans = 0
  while len(black_points) > 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:
        x = black_point[0] + vec[0]
        y = black_point[1] + vec[1]
        # target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if x < 0 or y < 0 or x >= W or y >= H or grid[y][x] == "#": continue
        grid[y][x] = "#"
        next_black_points.append((x, y))
    black_points = next_black_points
    ans += 1

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

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

  ans = 0
  while len(black_points) > 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 = (black_point[0] + vec[0], black_point[1] + vec[1])
        # target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if target_point[0] < 0: continue
        if target_point[1] < 0: continue
        if target_point[0] >= W: continue
        if target_point[1] >= H: continue
        if grid[target_point[1]][target_point[0]] == "#": continue
        grid[target_point[1]][target_point[0]] = "#"
        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 - 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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})"
    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 = []
  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 len(black_points) > 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 - 1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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})"
    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 = []
  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: Time Limit Exceeded

Solution code:
from collections import deque

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

dp = [[-1 for i in range(W)] for j in range(H)]
dir = [[1,0], [-1,0], [0,1], [0,-1]]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            dp[h][w] = 0
            data = deque([[h,w]])
            while len(data) > 0:
                i, j = data.popleft()

                for dx, dy in dir:
                    if i+dx < 0 or H-1 < i+dx or j+dy < 0 or W-1 < j+dy:
                        continue
                    if G[i+dx][j+dy] == "#":
                        continue
                    if dp[i+dx][j+dy] != -1 and dp[i+dx][j+dy] < dp[i][j] + 1:
                        continue
                    dp[i+dx][j+dy] = dp[i][j] + 1
                    data.append([i+dx,j+dy])

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])

print(ans)

Submission status: Time Limit Exceeded

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:
    i,j=b.popleft()
    
    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)))
   
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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=set()
br=set()
n=[-1]*(h*w)
c=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
             b.add((i,j))
             n[i*w+j]=0
        else:
            continue
while True:
    f=False
    update=False
    for z in b:
        i=z[0]
        j=z[1]
        if i<h-1 and a[i+1][j]=="." and n[(i+1)*w+j]==-1:
            br.add(((i+1),j))
            n[(i+1)*w+j]=0
            f=True
        if i>0 and a[i-1][j]=="." and n[(i-1)*w+j]==-1:
            br.add(((i-1),j))
            n[(i-1)*w+j]=0
            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)]=0
            br.add((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)]=0
            br.add((i,(j-1)))
    if f:
      c+=1
      update=True
    if not f:
      break
    b=set()
    b=b|br
    br=set()
print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

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

mx = [0,0,1,-1]
my = [1,-1,0,0]

ans = -1
def bfs(map_input,queue,ans):
    while queue:
        queue2 = deque([])
        ans+=1
        for x,y in queue:
            for i in range(4):
                nx = x+mx[i]
                ny = y+my[i]
                if 0<=nx<w and 0<=ny<h:
                    if map_input[ny][nx]=='#':
                        continue
                    map_input[ny][nx]='#'
                    queue2.append([nx,ny])

        queue = queue2
    return ans

ans = bfs(map_input,queue,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
map_input = [list(input()) for i in range(h)]

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

mx = [0,0,1,-1]
my = [1,-1,0,0]

ans = 0
def bfs(map_input,queue):
    queue2 = deque([])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+mx[i]
            ny = y+my[i]
            if 0<=nx<w and 0<=ny<h:
                if map_input[ny][nx]=='#':
                    continue
                map_input[ny][nx]='#'
                queue2.append([nx,ny])

    return queue2

while True:
    queue = bfs(map_input,queue)
    if len(queue)==0:
        break
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
a = [list(input()) for i in range(h)]
visit = [[-1 for i in range(w)] for j in range(h)]
d = deque()

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

p = [(1,0),(-1,0),(0,1),(0,-1)]
ans = 0
while d:
    x,y = d.popleft()
    for s,t in p:
        if 0 <= x+s <= h-1 and 0 <= y+t <= w-1:
            if visit[x+s][y+t] == -1:
                visit[x+s][y+t] = visit[x][y] + 1
                ans = max(ans,visit[x][y]+1)
                d.append((x+s,y+t))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque()
for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "#":
            q.append([i, j, 0])
            dist_map[i][j] = 0

max_dist = 0

while len(q) > 0:
    current_h, current_w, dist = q.popleft()
    if max_dist < dist:
        max_dist = dist
    dist_map[current_h][current_w] = dist
    for dir in range(4):
        nh = current_h + n_i[dir]
        nw = current_w + n_j[dir]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if dist_map[nh][nw] != INF:
            continue
        q.append((nh, nw, dist+1))


print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque([])
for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "#":
            q.append([i, j, 0])
            dist_map[i][j] = 0

max_dist = 0

while len(q) > 0:
    current = q.popleft()
    current_h = current[0]
    current_w = current[1]
    dist = current[2]

    if max_dist < dist:
        max_dist = dist
    dist_map[current_h][current_w] = dist
    for dir in range(4):
        nh = current_h + n_i[dir]
        nw = current_w + n_j[dir]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if dist_map[nh][nw] != INF:
            continue
        q.append((nh, nw, dist+1))


print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
a = [input() for i in range(H)]

dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque([])
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            q.append([i, j, 0])

max_dist = 0

while len(q) > 0:
    current = q.popleft()
    current_h = current[0]
    current_w = current[1]
    dist = current[2]
    if dist_map[current_h][current_w] != INF:
        continue
    if max_dist < dist:
        max_dist = dist
    dist_map[current_h][current_w] = dist
    for dir in range(4):
        nh = current_h + n_i[dir]
        nw = current_w + n_j[dir]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if a[nh][nw] == "#":
            continue
        q.append((nh, nw, dist+1))


print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
a = [input() for i in range(H)]

dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque([])
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            q.append([i, j, 0])

max_dist = 0
def update(c_h, c_w, d_map, dist, q):
    global max_dist
    if d_map[c_h][c_w] != INF:
        return
    if max_dist < dist:
        max_dist = dist
    d_map[c_h][c_w] = dist
    for dir in range(4):
        if c_h+n_i[dir] < 0 or H <= c_h+n_i[dir] or c_w+n_j[dir] < 0 or W <= c_w+n_j[dir]:
            continue
        if a[c_h+n_i[dir]][c_w+n_j[dir]] == "#":
            continue
        q.append((c_h+n_i[dir], c_w+n_j[dir], dist+1))

while len(q) > 0:
    current = q.popleft()
    current_h = current[0]
    current_w = current[1]
    dist = current[2]
    update(current_h, current_w, dist_map, dist, q)


print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
a = [input() for i in range(H)]

dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque([])
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            q.append([i, j, 0])

def update(c_h, c_w, d_map, dist, q):
    if d_map[c_h][c_w] != INF:
        return
    d_map[c_h][c_w] = dist
    for dir in range(4):
        if c_h+n_i[dir] < 0 or H <= c_h+n_i[dir] or c_w+n_j[dir] < 0 or W <= c_w+n_j[dir]:
            continue
        if a[c_h+n_i[dir]][c_w+n_j[dir]] == "#":
            continue
        q.append((c_h+n_i[dir], c_w+n_j[dir], dist+1))

while len(q) > 0:
    current = q.popleft()
    current_h = current[0]
    current_w = current[1]
    dist = current[2]
    update(current_h, current_w, dist_map, dist, q)

max_dist = 0
for i in range(H):
    for j in range(W):
        if max_dist < dist_map[i][j] and dist_map[i][j] != INF:
            max_dist = dist_map[i][j]
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
a = []
INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
for i in range(H):
    a.append(input())

dist_map = [[INF]*W for _ in range(H)]
# 黒マスの位置を記録
black_pos = []
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            black_pos.append([i, j])

def update(c_h, c_w, d_map, dist, q):
    if d_map[c_h][c_w] != INF:
        return
    d_map[c_h][c_w] = dist
    for dir in range(4):
        if c_h+n_i[dir] < 0 or H <= c_h+n_i[dir] or c_w+n_j[dir] < 0 or W <= c_w+n_j[dir]:
            continue
        if a[c_h+n_i[dir]][c_w+n_j[dir]] == "#":
            continue
        q.append((c_h+n_i[dir], c_w+n_j[dir], dist+1))

q = [(pos[0], pos[1], 0) for pos in black_pos]
while len(q) > 0:
    current = q.pop(0)
    current_h = current[0]
    current_w = current[1]
    dist = current[2]
    update(current_h, current_w, dist_map, dist, q)

max_dist = 0
for i in range(H):
    for j in range(W):
        if max_dist < dist_map[i][j] and dist_map[i][j] != INF:
            max_dist = dist_map[i][j]
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

Y,X=map(int,input().split())


cs=[list(input()) for i in range(Y)]
blacklist=[]
for i in range(Y):
    for j in range(X):
        if cs[i][j]=="#":
            blacklist.append([i,j])
            
dist0=[[[] for i in range(X)] for j in range(Y)]
for B in blacklist:
    dist=[[-1 for i in range(X)] for j in range(Y)]
    q=deque()
    sy=B[0]
    sx=B[1]
    dist[sy][sx]=0
    q.append([sy,sx])
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    while(len(q)!=0):
        v=q.popleft()
        for i in range(4):
            nv =[v[0]+dy[i], v[1]+dx[i]]
            if nv[0] < 0 or nv[0] > Y-1 or nv[1] < 0 or nv[1] > X-1:
                continue
            if dist[nv[0]][nv[1]] != -1:
                continue
            dist[nv[0]][nv[1]] = dist[v[0]][v[1]]+1
            q.append(nv)
    for i in range(Y):
        for j in range(X):
            dist0[i][j].append(dist[i][j])


for i in range(Y):
    for j in range(X):
        dist0[i][j]=min(dist0[i][j])
d=[max(dist0[i]) for i in range(Y)]
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)

ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)

ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])

for i in range(h):
    for j in range(w):
        if f[i][j] != '#':
            ans = max(ans,f[i][j])
print(ans)