問題: 迷路の最短経路 (Python)

迷路の最短経路 (Python)

問題

1行目に迷路の行数 h と列数 w、続く h 行に迷路を入力として受け取ります。'.' は通路、'#' は壁です。幅優先探索（BFS）を使って、左上のマスから右下のマスまで上下左右に移動するときの最短歩数を表示してください。到達できない場合はその旨を表示します。

入力例

5 7
..#....
.##.##.
...#...
.#...#.
...#...

出力例

最短歩数: 10

参照コード

コピーはできません。自分でタイピングしてください。

from collections import deque

def shortest_path(grid):
    """幅優先探索で左上から右下までの最短歩数を求める"""
    h, w = len(grid), len(grid[0])
    dist = [[-1] * w for _ in range(h)]
    dist[0][0] = 0
    queue = deque([(0, 0)])
    while queue:
        y, x = queue.popleft()
        if (y, x) == (h - 1, w - 1):
            return dist[y][x]
        for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ny, nx = y + dy, x + dx
            if 0 <= ny < h and 0 <= nx < w:
                if grid[ny][nx] == "." and dist[ny][nx] == -1:
                    dist[ny][nx] = dist[y][x] + 1
                    queue.append((ny, nx))
    return -1

def main():
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    steps = shortest_path(grid)
    if steps >= 0:
        print(f"最短歩数: {steps}")
    else:
        print("ゴールに到達できません")

if __name__ == "__main__":
    main()

迷路の最短経路 (Python)

問題

入力例

出力例

参照コード

入力エリア