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 subprocess import call
call (('pypy3', '-c', """
import collections

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

visited = [[-float("inf")]*w for _ in range(h)]
q = collections.deque([])

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

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

while 0 < len(q):
    cy, cx = q.pop()
    for i in range(4):
        x = cx + dx[i]
        y = cy + dy[i]

        if x < 0 or w <= x or y < 0 or h <= y:
            continue

        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans, visited[i][j])
print(ans)
"""))

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w = map(int, input().split())

visited = [[-float("inf")]*(w) for _ in range(h)]
q = collections.deque([])

a = []
for i in range(h):
    _a = list(input())
    a.append(_a)
    for j in range(w):
        if _a[j] == "#":
            q.appendleft([i, j])
            visited[i][j] = 0

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

while 0 < len(q):
    cy, cx = q.pop()
    for i in range(4):
        x = cx + dx[i]
        y = cy + dy[i]

        if x < 0 or w <= x or y < 0 or h <= y:
            continue

        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans, visited[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

h, w = map(int, input().split())

visited = [[-float("inf")]*(w) for _ in range(h)]
q = collections.deque([])

a = []
for i in range(h):
    _a = list(input())
    a.append(_a)
    for j in range(w):
        if _a[j] == "#":
            q.appendleft([i, j])
            visited[i][j] = 0

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

while 0 < len(q):
    cy, cx = q.pop()
    for _dx, _dy in zip(dx, dy):
        x = cx + _dx
        y = cy + _dy

        if x < 0 or w <= x or y < 0 or h <= y:
            continue

        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for v in visited:
    ans = max(ans, max(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
maze = [input() for i in range(h)]
route_total = [[h*w] * w for i in range(h)]

black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            black_list.append([i+1,j+1])
 
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

stack = MyStack()
for black in black_list:
    route = [[0] * w for i in range(h)]
    stack.push(black[0],black[1])
    route[black[0]-1][black[1]-1] = 0
    while len(stack.stack) > 0:
        y,x = stack.pop()
        route_num = route[y-1][x-1] + 1
        if y != h:
            if maze[y][x-1] == '.' and route[y][x-1] == 0:
                stack.push(y+1,x)
                route[y][x-1] = route_num
                route_total[y][x-1] = min(route_num,route_total[y][x-1])
        if y != 1:
            if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
                stack.push(y-1,x)
                route[y-2][x-1] = route_num
                route_total[y-2][x-1] = min(route_num,route_total[y-2][x-1])
        if x != w:
            if maze[y-1][x] == '.' and route[y-1][x] == 0:
                stack.push(y,x+1)
                route[y-1][x] = route_num
                route_total[y-1][x] = min(route_num,route_total[y-1][x])
        if x != 1:
            if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
                stack.push(y,x-1)
                route[y-1][x-2] = route_num
                route_total[y-1][x-2] = min(route_num,route_total[y-1][x-2])

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            ans = max(route_total[i][j],ans)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque

H, W = [int(i) for i in input().split()]
grid = [list(input()) for _ in range(H)]
reached = [[0] * W for _ in range(H)]

queue = deque()
for y, x in product(range(H), range(W)):
    if grid[y][x] == "#":
        queue.append((y, x, 0))

if len(queue) == H * W:
    print(0)
    exit()

ans = 0
while queue:
    y, x, steps = queue.popleft()
    if not (0 <= y < H and 0 <= x < W):
        continue
    if reached[y][x]:
        continue
    reached[y][x] = 1
    ans = max(ans, steps)
    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        queue.append((y+dy, x+dx, steps+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

queue = deque()
for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '#':
            queue.append((i, j))

while queue:
    # 先頭の値を取り出す
    h, w = queue.popleft()

    # 上下左右4マスに対し処理
    for i in range(4):

        # 移動距離
        dx, dy = dis_x[i], dis_y[i]

        # もし次のマスの黒塗りが終わっていないなら
        if s[h+dy][w+dx] == '.':
            s[h+dy][w+dx] = '#'
            dist[h+dy][w+dx] = dist[h][w] + 1

            queue.append((h+dy, w+dx))


print(max(max(l) for l in dist))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]


# 塗らなければいけないマスの数
target_count = sum(l.count('.') for l in s)

queue = deque()

for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '#':
            queue.append((i, j))

while queue:
    # 先頭の値を取り出す
    h, w = queue.popleft()

    # 上下左右4マスに対し処理
    for i in range(4):

        # 移動距離
        dx, dy = dis_x[i], dis_y[i]

        # もし次のマスが通路かつ黒塗りが終わっていないなら
        if s[h+dy][w+dx] == '.' and target_count != 0:
            s[h+dy][w+dx] = '#'
            dist[h+dy][w+dx] = dist[h][w] + 1
            target_count -= 1

            queue.append((h+dy, w+dx))


print(max(max(l) for l in dist))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# 上下左右1マスを検索するために必要とする
dis_x = [1, 0, -1, 0]
dis_y = [0, 1, 0, -1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
for _ in range(max_h):
    line = input()
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list("#{}#".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("#" * (max_w + 2))] + s + [list("#" * (max_w + 2))]

# 塗らなければいけないマスの数
target_count = sum(l.count('.') for l in s)

queue = deque()

for i in range(1, max_h+1):
    for j in range(1, max_w+1):
        if s[i][j] == '#':
            queue.append((i, j))

total_time = 0
while target_count != 0:
    next_queue = deque()
    while queue:
        # 先頭の値を取り出す
        h, w = queue.popleft()

        # 上下左右4マスに対し処理
        for i in range(4):

            # 移動距離
            dx, dy = dis_x[i], dis_y[i]

            # もし次のマスが通路かつ黒塗りが終わっていないなら
            if s[h+dy][w+dx] == '.' and target_count != 0:
                s[h+dy][w+dx] = '#'
                target_count -= 1

                next_queue.append((h+dy, w+dx))

    queue = next_queue
    total_time += 1

print(total_time)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    ans += 1
    qq = deque()
    while que:
      nh, nw = que.popleft()
      if nw < W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if nw > 0 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh < H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if nh > 0 and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    ans += 1
    qq = deque()
    while que:
      nh, nw = que.popleft()
      if nw<W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if nw>0 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh<H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if 0<nh and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([[i, j] for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    qq = deque()
    ans += 1
    while que:
      nh, nw = que.popleft()
      if nw<W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if  0<nw and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh<H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if 0<nh and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    qq = deque()
    ans += 1
    while que:
      nh, nw = que.popleft()
      if nw+1<=W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if  0<=nw-1 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh+1<=H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if 0<=nh-1 and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([[i, j] for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    qq = deque()
    ans += 1
    while que:
      nh, nw = que.popleft()
      if nw+1<=W-1 and not M[nh][nw+1]:
        qq.append([nh,nw+1])
        M[nh][nw+1] = True
      if  0<=nw-1 and not M[nh][nw-1]:
        qq.append([nh,nw-1])
        M[nh][nw-1] = True
      if nh+1<=H-1 and not M[nh+1][nw]:
        qq.append([nh+1,nw])
        M[nh+1][nw] = True
      if 0<=nh-1 and not M[nh-1][nw]:
        qq.append([nh-1,nw])
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([[i, j] for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and not M[nh][nw+1]:
        qq.append([nh,nw+1])
        M[nh][nw+1] = True
      if  0<=nw-1 and not M[nh][nw-1]:
        qq.append([nh,nw-1])
        M[nh][nw-1] = True
      if nh+1<=H-1 and not M[nh+1][nw]:
        qq.append([nh+1,nw])
        M[nh+1][nw] = True
      if 0<=nh-1 and not M[nh-1][nw]:
        qq.append([nh-1,nw])
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([[i, j] for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and not M[nh][nw+1]:
        qq.append([nh,nw+1])
        M[nh][nw+1] = True
      if  0<=nw-1 and not M[nh][nw-1]:
        qq.append([nh,nw-1])
        M[nh][nw-1] = True
      if nh+1<=H-1 and not M[nh+1][nw]:
        qq.append([nh+1,nw])
        M[nh+1][nw] = True
      if 0<=nh-1 and not M[nh-1][nw]:
        qq.append([nh-1,nw])
        M[nh-1][nw] = True
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  black = [[True]*W for _ in range(H)]
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = False
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and black[nh][nw+1] == True:
        qq.append([nh,nw+1])
        black[nh][nw+1] = False
      if  0<=nw-1 and black[nh][nw-1] == True:
        qq.append([nh,nw-1])
        black[nh][nw-1] = False
      if nh+1<=H-1 and black[nh+1][nw] == True:
        qq.append([nh+1,nw])
        black[nh+1][nw] = False
      if 0<=nh-1 and black[nh-1][nw] == True:
        qq.append([nh-1,nw])
        black[nh-1][nw] = False
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  black = [[0]*W for _ in range(H)]
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 1
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and black[nh][nw+1] == 0:
        qq.append([nh,nw+1])
        black[nh][nw+1] = 1
      if  0<=nw-1 and black[nh][nw-1] == 0:
        qq.append([nh,nw-1])
        black[nh][nw-1] = 1
      if nh+1<=H-1 and black[nh+1][nw] == 0:
        qq.append([nh+1,nw])
        black[nh+1][nw] = 1
      if 0<=nh-1 and black[nh-1][nw] == 0:
        qq.append([nh-1,nw])
        black[nh-1][nw] = 1
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  black = np.zeros((H,W))
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      if nw+1<=W-1 and black[nh][nw+1] == 0:
        qq.append([nh,nw+1])
        black[nh][nw+1] = black[nh][nw]+1
      if  0<=nw-1 and black[nh][nw-1] == 0:
        qq.append([nh,nw-1])
        black[nh][nw-1] = black[nh][nw]+1
      if nh+1<=H-1 and black[nh+1][nw] == 0:
        qq.append([nh+1,nw])
        black[nh+1][nw] = black[nh][nw]+1
      if 0<=nh-1 and black[nh-1][nw] == 0:
        qq.append([nh-1,nw])
        black[nh-1][nw] = black[nh][nw]+1
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      dh, dw = 0,1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 0,-1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = -1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    nh, nw = que.pop(0)
    dh, dw = 0,1
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = 0,-1
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = 1,0
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = -1,0
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    nh, nw = que.pop(0)
    dh, dw = 0,1
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = 0,-1
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = 1,0
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
    dh, dw = -1,0
    if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        que.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]

direction = [[0,1],[0,-1],[1,0],[-1,0]]
black = np.zeros((H,W))
que = []
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      que.append([i,j])
      black[i][j] = 0
def main():
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
        continue
      if black[nh+dh][nw+dw] > 0:
        continue
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

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

direction = [[0,1],[0,-1],[1,0],[-1,0]]
black = np.zeros((H,W))
que = []
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      que.append([i,j])
      black[i][j] = 0
def main():
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
        continue
      if black[nh+dh][nw+dw] > 0:
        continue
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
        continue
      if black[nh+dh][nw+dw] > 0:
        continue
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

direction = [[0,1],[0,-1],[1,0],[-1,0]]
black = np.zeros((H,W))
que = []
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      que.append([i,j])
      black[i][j] = 0
def main():
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
        continue
      if black[nh+dh][nw+dw] > 0:
        continue
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

direction = [[0,1],[0,-1],[1,0],[-1,0]]
black = np.zeros((H,W))
que = []
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      que.append([i,j])
      black[i][j] = 0

while que:
  nh, nw = que.pop(0)
  for dh, dw in direction:
    if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
      continue
    if black[nh+dh][nw+dw] > 0:
      continue
    que.append([nh+dh,nw+dw])
    black[nh+dh][nw+dw] = black[nh][nw]+1
print(int(np.max(black)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
A = [input() for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      que.append((i, j))
      dist[i][j] = 0
ans = 0
while que:
  y, x = que.popleft()
  for dy, dx in zip(di, dj):
    ny, nx = y+dy, x+dx
    if ny < 0 or ny >= h or nx < 0 or nx >= w:
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    ans = max(ans, dist[ny][nx])
    que.append((ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
h, w = map(int, input().split())
A = [input() for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
que = deque()
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      que.append((i, j))
      dist[i][j] = 0
while que:
  y, x = que.popleft()
  for dy, dx in zip(di, dj):
    ny, nx = y+dy, x+dx
    if ny < 0 or ny >= h or nx < 0 or nx >= w:
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.append((ny, nx))
print(np.array(dist).max())

Submission status: Time Limit Exceeded

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

from collections import deque

h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

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

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while q:
    # queue の先頭を取り出す
    x, y, dist = q.popleft()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.append( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)

Submission status: Time Limit Exceeded

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

from queue import Queue
# from collections import deque

h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

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

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = Queue()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.put( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while not q.empty():
    # queue の先頭を取り出す
    x, y, dist = q.get()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.put( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
  h,w=map(int,input().split())
  ans,q=0,deque()
  visited=[[0 if j=="#" else -1 for j in input()] for _ in range(h)]
  q=deque([(i,j) for i in range(h) for j in range(w) if visited[i][j]==0])
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if visited[newx][newy]==-1:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[list(input()) for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
ans,b,q=0,[],deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
while q:
  x,y=q.popleft()
  for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
    newx,newy=x+i,y+j
    if 0<=newx<h and 0<=newy<w:
      if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
        visited[newx][newy]=visited[x][y]+1
        q.append([newx,newy])
        ans=max(ans,visited[newx][newy])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
ans,b,q=0,[],deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
while q:
  x,y=q.popleft()
  for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
    newx,newy=x+i,y+j
    if 0<=newx<h and 0<=newy<w:
      if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
        visited[newx][newy]=visited[x][y]+1
        q.append([newx,newy])
        ans=max(ans,visited[newx][newy])
print(ans)