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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
# from copy import deepcopy


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

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

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


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

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

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


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

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



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

start_list = deque()

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

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


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

Submission status: Time Limit Exceeded

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

from collections import deque
from copy import deepcopy

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

start_list = []

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

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

def bfs():

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

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


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

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

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


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

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


print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(input()))
q = deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i, j, 0))
dxdy = [(-1, 0), (0, -1), (0, 1), (1, 0)]
ans = 0
while q:
    y, x, cnt = q.popleft()
    for dx, dy in dxdy:
        if not(0<=x+dx<w and 0<=y+dy<h):
            continue
        if a[y+dy][x+dx]=='.':
            a[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, cnt+1))
            ans = cnt+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())


HW=[ [-1 for w in range(W)] for h in range(H) ]

#print(HW)
from collections import deque
Q = deque()

for h in range(H):
  S = input()
  for w in range(W):
    if S[w]=="#":
      Q.append([h,w])
      HW[h][w]=0

X = [0,0,-1,1]
Y = [-1,1,0,0]
ans=0

while Q:
  h,w = Q.popleft()

  for i in range(len(X)):
    ih,iw = h + Y[i], w + X[i]

    if not ((0 <= ih < H) and (0 <= iw < W)): continue
    if HW[ih][iw] >= 0: continue

    HW[ih][iw] = HW[h][w]+1
    ans = max(ans, HW[ih][iw])
    Q.append([ih,iw])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int, input().split())

m = [list(input()) for _ in range(h)]

def get_start_points(m):
    start_points = []
    for y in range(h):
        for x in range(w):
            if m[y][x] == '#':
                start_points.append((y,x))
    return start_points

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for q in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '#'
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(get_start_points(m)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

def bfs(sx, sy):
    q = deque([])
    d = [[-1 for _ in range(W)] for _ in range(H)]
    q.append([sx, sy])
    d[sy][sx] = 0
    
    while(q):
        pop = q.popleft()
        x, y = pop[0], pop[1]
        if A[y][x] == "#":
            return d[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and ny >= 0 and ny < H:
                if d[ny][nx] == -1:
                    q.append([nx, ny])
                    d[ny][nx] = d[y][x] + 1

                 
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == ".":
            res = bfs(i, j)
            ans = max(res, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
index, ans, que, A = 0, 0, deque([]), []
for _ in range(H):
    a = input()
    A += list(a)
    for x in a:
        if x == "#":
            que.append(index)
        index += 1

while len(que) > 0:
    nque = deque([])
    while len(que) > 0:
        i = que.popleft()
        if i > W-1 and A[i-W] == '.':
            nque.append(i-W)
            A[i-W] = '#'
        if i < (H-1)*W and A[i+W] == '.':
            nque.append(i+W)
            A[i+W] = '#'
        if i % W != 0 and A[i-1] == '.':
            nque.append(i-1)
            A[i-1] = '#'
        if i % W != W-1 and A[i+1] == '.':
            nque.append(i+1)
            A[i+1] = '#'
    que = copy.copy(nque)
    ans += 1

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
from collections import Counter, defaultdict, deque
from heapq import heappush
from itertools import chain, combinations, permutations


def resolve():
    H, W = map(int, sys.stdin.readline().strip().split())
    matrix = [[] for _ in range(H)]
    for i in range(H):
        matrix[i] = list(sys.stdin.readline().strip())

    start = [(i, j) for i in range(H) for j in range(W) if matrix[i][j] == '#' ]
    queue = deque(start)
    ans = -1
    while queue:
        len_queue = len(queue)
        ans += 1
        for _ in range(len_queue):
            x, y = queue.popleft()
            if x+1 < H and matrix[x+1][y] == '.':
                matrix[x+1][y] = '#'
                queue.append((x+1, y))
            if 0 <= x-1 and matrix[x-1][y] == '.':
                matrix[x-1][y] = '#'
                queue.append((x-1, y))
            if y+1 < W and matrix[x][y+1] == '.':
                matrix[x][y+1] = '#'
                queue.append((x, y+1))
            if 0 <= y-1 and matrix[x][y-1] == '.':
                matrix[x][y-1] = '#'
                queue.append((x, y-1))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
from collections import Counter, defaultdict, deque
from heapq import heappush
from itertools import chain, combinations, permutations


def resolve():
    H, W = map(int, sys.stdin.readline().strip().split())
    matrix = [None] * H
    for i in range(H):
        matrix[i] = list(sys.stdin.readline().strip())

    start = [(i, j) for i in range(H) for j in range(W) if matrix[i][j] == '#' ]
    queue = deque(start)
    ans = -1
    while queue:
        len_queue = len(queue)
        ans += 1
        for _ in range(len_queue):
            x, y = queue.popleft()
            nexts = (
                (x+1, y),
                (x-1, y),
                (x, y+1),
                (x, y-1),
            )
            for nx, ny in nexts:
                if 0 <= nx < H and 0 <= ny < W and matrix[nx][ny] == '.':
                    matrix[nx][ny] = '#'
                    queue.append((nx, ny))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
from collections import Counter, defaultdict, deque
from heapq import heappush
from itertools import chain, combinations, permutations


def resolve():
    H, W = map(int, sys.stdin.readline().strip().split())
    matrix = [None] * H
    for i in range(H):
        matrix[i] = list(sys.stdin.readline().strip())

    start = []
    for i, row in enumerate(matrix):
        for j, cell in enumerate(row):
            if cell == '#':
                start.append((i, j))

    queue = deque(start)
    ans = -1
    while queue:
        len_queue = len(queue)
        ans += 1
        for _ in range(len_queue):
            x, y = queue.popleft()
            nexts = (
                (x+1, y),
                (x-1, y),
                (x, y+1),
                (x, y-1),
            )
            for nx, ny in nexts:
                if 0 <= nx < H and 0 <= ny < W and matrix[nx][ny] == '.':
                    matrix[nx][ny] = '#'
                    queue.append((nx, ny))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H,W = map(int,sys.stdin.readline().rstrip().split())
map = [[i for i in map(str,sys.stdin.readline().rstrip())] for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if map[i][j] == '#':
      q.append((i,j))
      dist[i][j] = 0

def bfs():
  while q:
    x,y = q.popleft()
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0<= nx < H and 0 <= ny < W and map[nx][ny] == '.' and dist[nx][ny] == -1:
        dist[nx][ny] = dist[x][y] + 1
        q.append((nx,ny))
bfs()
ans = 0
for i in range(H):
  ans = max(max(dist[i][:]),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
A = [input() for _ in range(H)]

inf = 10**6
d = [[inf]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == ".":
            continue
        q = deque()
        q.append((i, j, 0))
        d[i][j] = 0
        while q:
            temp = q.popleft()
            x = temp[0]
            y = temp[1]
            r = temp[2]
            if x > 0 and d[x-1][y] > r+1:
                d[x-1][y] = r+1
                q.append((x-1, y, r+1))
            if y > 0 and d[x][y-1] > r+1:
                d[x][y-1] = r+1
                q.append((x, y-1, r+1))
            if x < H-1 and d[x+1][y] > r+1:
                d[x+1][y] = r+1
                q.append((x+1, y, r+1))
            if y < W-1 and d[x][y+1] > r+1:
                d[x][y+1] = r+1
                q.append((x, y+1, r+1))

ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Q = deque([])
A = []
stamp = [[-1]*w for _ in range(h)]
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            Q.append([i, j])
            stamp[i][j] = 0
    A.append(line)

while Q:
    row, col = Q.popleft()
    for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        new_row, new_col = row+i, col+j
        if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w or stamp[new_row][new_col] != -1:
            continue
        stamp[new_row][new_col] = stamp[row][col] + 1
        Q.append([new_row, new_col])

print(max([max(i) for i in stamp]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Q = deque([])
A = []
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            Q.append([i, j])
    A.append(line)
stamp = [[0]*w for _ in range(h)]

while Q:
    row, col = Q.popleft()
    for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        new_row, new_col = row+i, col+j
        if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w or stamp[new_row][new_col] > 0:
            continue
        stamp[new_row][new_col] = stamp[row][col] + 1
        Q.append([new_row, new_col])

print(max([max(i) for i in stamp]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Q = deque([])
A = []
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            Q.append([i, j])
    A.append(line)
stamp = [[0]*w for _ in range(h)]

while Q:
    row, col = Q.popleft()
    for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
        new_row, new_col = row+i, col+j
        if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w:
            continue
        if stamp[new_row][new_col] > 0:
            continue
        stamp[new_row][new_col] = stamp[row][col] + 1
        Q.append([new_row, new_col])

print(max([max(i) for i in stamp]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Q = deque([])
A = []
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            Q.append([i, j])
    A.append(line)
stamp = [[0]*w for _ in range(h)]

ans = 0
while Q:
    new_Q = deque([])
    while Q:
        row, col = Q.popleft()
        stamp[row][col] = 1
        for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
            new_row, new_col = row+i, col+j
            if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w:
                continue
            if A[new_row][new_col] == '#' or stamp[new_row][new_col] == 1:
                continue
            A[new_row][new_col] = '#'
            new_Q.append([new_row, new_col])
    if len(new_Q) == 0:
        break
    Q = new_Q
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Q = deque([])
A = []
for i in range(h):
    line = list(input())
    for j in range(w):
        if line[j] == '#':
            Q.append([i, j])
    A.append(line)

ans = 0
while Q:
    new_Q = deque([])
    while Q:
        row, col = Q.popleft()
        for i, j in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
            new_row, new_col = row+i, col+j
            if new_row < 0 or new_row >= h or new_col < 0 or new_col >= w:
                continue
            if A[new_row][new_col] == '#':
                continue
            A[new_row][new_col] = '#'
            new_Q.append([new_row, new_col])
    if len(new_Q) == 0:
        break
    Q = new_Q
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''


■考え方
以下を繰り返し、白マスがなくなった時点のカウンターが答え。
1.黒マスに隣接する白マスを黒マスに塗り替える
2.カウンターに+1する

1詳細
1-0.現在の黒マスを全てキューへ入れる
1-1.キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
1-2. 1-1を繰り返し


'''
## import
from collections import deque # キュー、スタックに利用
# import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = True


black_str = '#'
white_str = '.'

def paint(q,M,h,w):
    '''
    キューから黒マスの位置を取り出し、隣接マスを「黒に塗り、キューへ入れる」
    '''
    out_q = deque()
    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]
    
    while len(q) > 0:
        # 探索する頂点uを取り出し
        y, x = q.popleft()

        ## uに隣接する全ての頂点について、白い場合は黒く塗り、out_qへ追加
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # h,wの範囲に収まっていなければスキップ
            if after_y < 0 or after_y > h-1 or after_x < 0 or after_x > w-1:
                continue

            if M[after_y][after_x] == white_str:
                M[after_y][after_x] = black_str
                # out_qに追加
                out_q.append([after_y,after_x]) # キューに追加
    
    return out_q


def main():
    '''メイン処理'''

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

    ans = 0
    # 塗るマスの位置を保持するキューを初期化
    q = deque()

    while True:
        ## 全てのマスが黒になったら終了
        # 以下の処理を入れると遅いのでコメントアウト
        # if white_str not in list(itertools.chain.from_iterable(M)):
        #     break

        # 各ターンで塗るマス。1=blackに塗るマス
        # paint_M = [[0]*w for _ in range(h)

        # 初回の場合、現在の黒マスを全てキューへ入れる
        if ans == 0:
            for i in range(h):
                for j in range(w):
                    if M[i][j] == black_str:
                        q.append([i,j])
        
        # キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
        q = paint(q,M,h,w)
        # 全てのマスが黒になったら終了
        if len(q) == 0:
            break

        ans += 1

    print(ans)


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Time Limit Exceeded

Solution code:
'''


■考え方
以下を繰り返し、白マスがなくなった時点のカウンターが答え。
1.黒マスに隣接する白マスを黒マスに塗り替える
2.カウンターに+1する

1詳細
1-0.現在の黒マスを全てキューへ入れる
1-1.キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
1-2. 1-1を繰り返し


'''
## import
from collections import deque # キュー、スタックに利用
import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = True


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

M = [list(input().rstrip()) for _ in range(h)]

black_str = '#'
white_str = '.'

def paint(q):
    '''
    キューから黒マスの位置を取り出し、隣接マスを「黒に塗り、キューへ入れる」
    '''
    out_q = deque()
    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]
    
    while len(q) > 0:
        # 探索する頂点uを取り出し
        y, x = q.popleft()

        ## uに隣接する全ての頂点について、白い場合は黒く塗り、out_qへ追加
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # h,wの範囲に収まっていなければスキップ
            if after_y < 0 or after_y > h-1 or after_x < 0 or after_x > w-1:
                continue

            if M[after_y][after_x] == white_str:
                M[after_y][after_x] = black_str
                # out_qに追加
                out_q.append([after_y,after_x]) # キューに追加
    
    return out_q


def main():
    '''メイン処理'''
    ans = 0
    # 塗るマスの位置を保持するキューを初期化
    q = deque()

    while True:
        ## 全てのマスが黒になったら終了
        # 以下の処理を入れると遅いのでコメントアウト
        # if white_str not in list(itertools.chain.from_iterable(M)):
        #     break

        # 各ターンで塗るマス。1=blackに塗るマス
        # paint_M = [[0]*w for _ in range(h)

        # 初回の場合、現在の黒マスを全てキューへ入れる
        if ans == 0:
            for i in range(h):
                for j in range(w):
                    if M[i][j] == black_str:
                        q.append([i,j])
        
        # キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
        q = paint(q)
        # 全てのマスが黒になったら終了
        if len(q) == 0:
            break

        ans += 1

    print(ans)


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Time Limit Exceeded

Solution code:
'''


■考え方
以下を繰り返し、白マスがなくなった時点のカウンターが答え。
1.黒マスに隣接する白マスを黒マスに塗り替える
2.カウンターに+1する

1詳細
1-0.現在の黒マスを全てキューへ入れる
1-1.キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
1-2. 1-1を繰り返し


'''
## import
from collections import deque # キュー、スタックに利用
import itertools
# import math # 数学的計算に利用
# import numpy as np # 行列計算などに利用
import sys

## 初期設定
input = sys.stdin.readline # 標準入力の高速化に利用
sys.setrecursionlimit(10**7) # 再帰関数の呼び出し上限を増やす
inf = float('inf')

is_debug = True


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

M = [list(input().rstrip()) for _ in range(h)]

black_str = '#'
white_str = '.'

def paint(q):
    '''
    キューから黒マスの位置を取り出し、隣接マスを「黒に塗り、キューへ入れる」
    '''
    out_q = deque()
    # 探索時の移動方向（上右下左） # delta y, delta x
    deltas = [[-1,0], [0,1], [1,0], [0,-1]]
    
    while len(q) > 0:
        # 探索する頂点uを取り出し
        y, x = q.popleft()

        ## uに隣接する全ての頂点について、白い場合は黒く塗り、out_qへ追加
        for delta in deltas:
            # 移動後の位置を算出
            after_y = y+delta[0]
            after_x = x+delta[1]
            # h,wの範囲に収まっていなければスキップ
            if after_y < 0 or after_y > h-1 or after_x < 0 or after_x > w-1:
                continue

            if M[after_y][after_x] == white_str:
                M[after_y][after_x] = black_str
                # out_qに追加
                out_q.append([after_y,after_x]) # キューに追加
    
    return out_q


def main():
    '''メイン処理'''
    ans = 0
    # 塗るマスの位置を保持するキューを初期化
    q = deque()

    while True:
        # 全てのマスが黒になったら終了
        if white_str not in list(itertools.chain.from_iterable(M)):
            break

        # 各ターンで塗るマス。1=blackに塗るマス
        # paint_M = [[0]*w for _ in range(h)

        # 初回の場合、現在の黒マスを全てキューへ入れる
        if ans == 0:
            for i in range(h):
                for j in range(w):
                    if M[i][j] == black_str:
                        q.append([i,j])
        
        # キューから取り出し、隣接マスを「黒に塗り、キューへ入れる」
        q = paint(q)

        ans += 1

    print(ans)


if __name__ == "__main__":
    # ファイル実行時に、main()関数を実行
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if 0<=nv[0]<self.H and 0<=nv[1]<self.W:
                    if self.dist[nv[0]][nv[1]] != -1:
                        continue
                    self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                    self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                sv_arr.append([i,j])
    bfs.bfs(sv_arr)
    cnt = max(sum(bfs.dist,[]))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while len(self.que)>0:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if 0<=nv[0]<self.H and 0<=nv[1]<self.W:
                    if self.dist[nv[0]][nv[1]] != -1:
                        continue
                    self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                    self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                sv_arr.append([i,j])
    bfs.bfs(sv_arr)
    cnt = max(sum(bfs.dist,[]))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while len(self.que)>0:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if 0<=nv[0]<self.H and 0<=nv[1]<self.W:
                    if self.dist[nv[0]][nv[1]] != -1:
                        continue
                    self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                    self.que.append(nv)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                sv_arr.append([i,j])
    bfs.bfs(sv_arr)
    cnt = max(sum(bfs.dist,[]))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
m = ["#"*(w+2)]+["#"+input()+"#" for i in range(h)]+["#"*(w+2)]
temp = [[-1]*(w+2) for i in range(h+2)]
opt = [(1,0),(0,1),(-1,0),(0,-1)]
dq = deque()
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
        if m[i][j] == "#":
            dq.append((i,j))
            temp[i][j] = 0
while dq:
    y,x = dq.popleft()
    for i in opt:
        y1 = y+i[0]
        x1 = x+i[1]
        if m[y1][x1] == "." and temp[y1][x1] == -1:
            temp[y1][x1] = temp[y][x]+1
            ans = max(ans,temp[y1][x1])
            dq.append((y1,x1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v_arr):
        # 初期条件(0-indexed)
        for start_v in start_v_arr:
            self.dist[start_v] = 0
            self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    start_v_arr = []
    for v, val in enumerate(bfs.val):
        if val == '#':
            start_v_arr.append(v)
    bfs.bfs(start_v_arr)
    cnt = max(bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)