AtCoder Beginner Contest 088 D – Grid Repainting をPython3で解く

# AtCoder Beginner Contest 088 D - Grid Repainting
# https://atcoder.jp/contests/abc088/tasks/abc088_d
# tag: グリッド BFS 典型問題 すぬけ君 一人ゲーム

# 最短手数で (1, 1) から (H, W) までたどり着くルートを見つけ、
# その時通ったマス以外を全て黒に塗ったときが答え。
# BFS で最短距離を求めればいい。

from collections import deque
def main():
    H, W = map(int, input().split())
    field = [input() for _ in range(H)]

    dist = [[0] * W for _ in range(H)]

    # すでにある黒マスの数を数えておく
    n_black = sum(row.count('#') for row in field)

    # インデックスを合わせて、スタートは (0, 0)
    # ゴールは (W-1, H-1) としておく
    # グリッドをBFSで全探索しつつ、スタートからの
    # 歩数を求めていく
    moves = ((-1, 0), (1, 0), (0, -1), (0, 1))
    queue = deque([(0, 0)])
    while queue:
        # 左から次の地点を取得(BFS)
        x_now, y_now = queue.popleft()
        dist_now = dist[y_now][x_now]

        # 次の地点を見ていく
        for dx, dy in moves:
            x_nxt, y_nxt = x_now + dx, y_now + dy
            # 範囲外ならスキップ
            if not (0 <= x_nxt < W and 0 <= y_nxt < H):
                continue
            # 壁 or 探索済みならスキップ
            if field[y_nxt][x_nxt] == '#' or dist[y_nxt][x_nxt] != 0:
                continue
            # 次の地点の距離を現在地 +1 に確定し、探索キューに入れる
            dist[y_nxt][x_nxt] = dist_now + 1
            queue.append((x_nxt, y_nxt))

    # ゴールにたどり着けない場合
    if dist[H-1][W-1] == 0:
        print(-1)

    # ゴールまでの歩数 + 1 マスの白マスが必要
    # 残りを全て黒マスにする（もともと黒マスのところはそのまま）
    else:
        print((H * W) - dist[H-1][W-1] - 1 - n_black)

main()