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:
import sys
from io import StringIO
import unittest
# from collections import deque
import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()
    # que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "#":
                que.put((i, j))
                # que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while not que.empty():
    # while len(que) > 0:

        now = que.get()
        # now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)
            # que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
from collections import deque
# import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    # grid = [["" for i in range(w)] for j in range(h)]
    # grid = [[-1 for i in range(w)] for j in range(h)]

    #for i in range(h):
    #    # grid[i] = list(input())
    #    grid[i] = list(input())

        # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
        # 1000×1000件で50ミリ秒くらい差が出る?
        # line = input()
        # for j in range(w):
        #     grid[i][j] = line[j:j+1]


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    # distance = [[-1 for i in range(w)] for j in range(h)]
    distance = [[-1 for i in range(w)] for j in range(h)]
    # que = queue.Queue()
    que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "#":
                # que.put((i, j))
                que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while len(que) > 0:

        # now = que.get()
        now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            # 黒塗りされているなら何もしない
            # この条件、不要な気がする・・
            # if grid[target[0]][target[1]] == '#':
            #     continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            # que.put(target)
            que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

            # 黒塗り
            # この処理、不要な気がする・・
            # grid[target[0]][target[1]] = '#'

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
from collections import deque
# import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    # grid = [["" for i in range(w)] for j in range(h)]
    # grid = [[-1 for i in range(w)] for j in range(h)]

    #for i in range(h):
    #    # grid[i] = list(input())
    #    grid[i] = list(input())

        # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
        # 1000×1000件で50ミリ秒くらい差が出る?
        # line = input()
        # for j in range(w):
        #     grid[i][j] = line[j:j+1]


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    # distance = [[-1 for i in range(w)] for j in range(h)]
    distance = [[-1 for i in range(w)] for j in range(h)]
    # que = queue.Queue()
    que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "#":
                # que.put((i, j))
                que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while len(que) > 0:

        # now = que.get()
        now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            # この条件、不要な気がする・・
            # if grid[target[0]][target[1]] == '#':
            #     continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            # que.put(target)
            que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

            # 黒塗り
            # この処理、不要な気がする・・
            # grid[target[0]][target[1]] = '#'

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# import queue
from collections import deque


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

grid = [["" for i in range(w + 2)] for j in range(h + 2)]

for i in range(h):
    grid[i] = list(input())

    # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
    # 1000×1000件で50ミリ秒くらい差が出る?
    # line = input()
    # for j in range(w):
    #     grid[i][j] = line[j:j+1]


# ★exec
# BFSにて最短経路を求める
# 準備
distance = [[-1 for i in range(w)] for j in range(h)]
# que = queue.Queue()
que = deque()

# スタート地点の情報を設定
# 多点スタートの設定
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            # que.put((i, j))
            que.append((i, j))
            distance[i][j] = 0

# BFS開始
while len(que) > 0:

    # now = que.get()
    now = que.popleft()

    # 上下左右のマスを確認
    for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

        # 盤の範囲外なら何もしない
        target = (now[0] + move_y, now[1] + move_x)
        if not h > target[0] >= 0 or not w > target[1] >= 0:
            continue

        # 黒塗りされているなら何もしない
        # この条件、不要な気がする・・
        # if grid[target[0]][target[1]] == '#':
        #     continue

        # 距離が設定済みなら何もしない
        if not distance[target[0]][target[1]] == -1:
            continue

        # キューに追加
        # que.put(target)
        que.append(target)
        # 最短距離を設定
        distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

        # 黒塗り
        # この処理、不要な気がする・・
        # grid[target[0]][target[1]] = '#'

# 距離が最大の点 = 答えになる。
ans = 0
for i in range(h):
    ans = max(ans, max(distance[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
from collections import deque
# import queue
from collections import deque


def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w + 2)] for j in range(h + 2)]

    for i in range(h):
        grid[i] = list(input())

        # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
        # 1000×1000件で50ミリ秒くらい差が出る?
        # line = input()
        # for j in range(w):
        #     grid[i][j] = line[j:j+1]


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    # que = queue.Queue()
    que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                # que.put((i, j))
                que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while len(que) > 0:

        # now = que.get()
        now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            # この条件、不要な気がする・・
            # if grid[target[0]][target[1]] == '#':
            #     continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            # que.put(target)
            que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

            # 黒塗り
            # この処理、不要な気がする・・
            # grid[target[0]][target[1]] = '#'

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put((i, j))
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

			# 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # 黒塗りされているなら何もしない
            # if grid[target[0]][target[1]] == '#':
            #    continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

			# 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from subprocess import call
call (('pypy3', '-c', """
import queue
 
def main():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)
    
    return
    
main()
 
"""))

Submission status: Time Limit Exceeded

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = list(input())
        for j in range(w):
            grid[i][j] = line[j]
        # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
        # 1000×1000件で50ミリ秒くらい差が出る。
        # line = input()
        # for j in range(w):
        #     grid[i][j] = line[j:j+1]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.append([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.__len__() == 0:

        now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.append(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = list(input())
        for j in range(w):
            grid[i][j] = line[j]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = input()
        for j in range(w):
            grid[i][j] = line[j:j+1]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = input()
        for j in range(w):
            grid[i][j] = line[j:j+1]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def search(x, y, d):
    if not (0 <= x < W and 0 <= y < H):
        return
    if d >= dist[y][x]:
        return
    dist[y][x] = d
    q.append([x, y, d])
    return
 
H, W = map(int, input().split())
q = deque()
field = [list(input()) for _ in range(H)]
dist = [[99999 for _ in range(W)] for __ in range(H)]
 
for y, row in enumerate(field):
    for x in [x for x, p in enumerate(row) if p == "#"]:
        search(x, y, 0)
 
while q:
    x,y,d = q.popleft()
    search(x-1, y, d+1)
    search(x+1, y, d+1)
    search(x, y-1, d+1)
    search(x, y+1, d+1)
 
print(max(list(map(max, dist))))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

def search(x, y, d):
    if not (0 <= x < W and 0 <= y < H):
        return
    if d >= dist[y][x]:
        return
    dist[y][x] = d
    q.put([x, y, d])
    return

H, W = map(int, input().split())
q = Queue()
field = [list(input()) for _ in range(H)]
dist = [[99999 for _ in range(W)] for __ in range(H)]

for y, row in enumerate(field):
    for x in [x for x, p in enumerate(row) if p == "#"]:
        search(x, y, 0)

while not q.empty():
    x,y,d = q.get()
    search(x-1, y, d+1)
    search(x+1, y, d+1)
    search(x, y-1, d+1)
    search(x, y+1, d+1)

print(max(list(map(max, dist))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, visited, s, h, w):
  queue = deque(s)
  #　返り値
  va = 0
  while queue:
    y,x = queue.popleft()
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_x < 0 or new_x >= w or new_y < 0 or new_y >=h :
        continue
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        #　移動回数の計算
        visited[new_y][new_x] = visited[y][x] + 1
        va = max(va,visited[new_y][new_x])
        queue.append([new_y, new_x])
  return va
############

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

maze = [['.' for j in range(w)] for i in range(h)]
visited = [[-1]*(w) for _ in range(h)]
s = []
s_append = s.append
for i in range(h) :
  m1 = input()
  for j in range(w) :
    if m1[j] == '#' :
      s_append([i,j])
      visited[i][j] = 0

print(bfs(maze, visited, s, h, w))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(maze, visited, s, h, w):
  queue = deque(s)
  #　返り値
  va = 0
  while queue:
    y,x = queue.popleft()
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
      new_y, new_x = y+j, x+k
      if new_x < 0 or new_x >= w or new_y < 0 or new_y >=h :
        continue
      if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
        #　移動回数の計算
        visited[new_y][new_x] = visited[y][x] + 1
        va = max(va,visited[new_y][new_x])
        queue.append([new_y, new_x])
  return va
############

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

maze = [['' for j in range(w)] for i in range(h)]
for i in range(h) :
  m1 = input()
  for j in range(w) :
    maze[i][j] = m1[j]

visited = [[-1]*(w) for _ in range(h)]
ans = []
s = []
s_append = s.append
for sy in range(h) :
  for sx in range(w):
    if maze[sy][sx] == '#' :
      s_append([sy,sx])
      maze[sy][sx] = '.'
      visited[sy][sx] = 0

print(bfs(maze, visited, s, h, w))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
m = [input() for _ in range(h)]
vm  = [[-1] * w for _ in range(h) ]

q = deque()

for i in range(h):
    for j in range(w):
        if m[i][j] == '#':
            q.append((i,j))
            vm[i][j]=0

while q:
    y,x = q.popleft()
    d = vm[y][x]

    for i,j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        yi , xj = y + i , x + j
        if yi >= 0 and xj >= 0 and yi < h and xj < w and vm[yi][xj] == -1 :
            vm[yi][xj] = d +  1
            q.append([yi,xj])
            

print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

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

m = 0
while q:
    y,x = q.popleft()
    for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
        ny = y + j
        nx = x + i
        if ny==-1 or nx==-1 or ny==h or nx==w:
            pass
        elif field[ny][nx]=="#":
            pass
        elif d[ny][nx]!=float("inf"):
            pass
        else:
            field[ny][nx] = "#"
            d[ny][nx] = d[y][x] + 1
            m = max(m,d[ny][nx])
            q.append([ny,nx])
print(m)