Problem p03053 (python)

Fixed submission:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Buggy submission (verdict: Runtime Error):
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 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()

Buggy submission (verdict: Runtime Error):
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]
            target_y = now_y + move_y
            target_x = now_x + move_x
            # if not h > target[0] >= 0 or not w > target[1] >= 0:
            if not h > target_y >= 0 or not w > target_x >= 0:
                continue

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

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

            # キューに追加
            que.put([target_y, target_x])

            # 最短距離を設定
            distance[target_y][target_x] = distance[now_y][now_x] + 1

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

    print(ans)


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
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.Deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    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()

Buggy submission (verdict: Runtime Error):
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.Deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    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()

Buggy submission (verdict: Runtime Error):
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.Deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    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()