概要

\(N \times N\) の迷路で、スタート S からゴール G まで上下左右に移動したときの、通るマス数の最小値を求める問題です。

各移動のコストはすべて \(1\) なので、最短経路は幅優先探索（BFS）で求められます。

考察

この問題では、各マスを頂点、隣接する通行可能なマス同士を辺と考えると、グリッドはグラフとして見ることができます。

移動は上下左右の隣接マスへのみ可能で、どの移動も \(1\) 手です。つまり、すべての辺の重みが等しいグラフにおける最短距離を求める問題になります。

このような場合、幅優先探索（BFS）が適しています。

例えば、スタートから近い順にマスを探索していくと、あるマスに初めて到達したときの距離が、そのマスへの最短距離になります。

一方で、単純な DFS で進めると、最初に見つけた経路が最短とは限りません。また、すべての経路を列挙しようとすると、経路数が非常に多くなり、\(N \leq 500\) では到底間に合いません。

したがって、各マスを高々一度だけ訪問する BFS によって効率よく最短経路を求めます。

また、この問題で求めるのは「移動回数」ではなく「通るマスの数」です。
そのため、スタート地点の距離を \(0\) ではなく \(1\) としておくと、ゴールに到達したときの値をそのまま答えとして出力できます。

アルゴリズム

次の手順で BFS を行います。

1. グリッドを読み込む
2. S と G の位置を探す
3. 各マスまでの最短距離を管理する配列 dist を用意する
   • 未訪問のマスは -1
   • スタート地点は 1
4. キューにスタート地点を入れる
5. キューが空になるまで以下を繰り返す
   • キューの先頭から現在位置を取り出す
   • もし現在位置がゴールなら、その距離を出力して終了
   • 上下左右の隣接マスを調べる
   • グリッド内であり、壁 # でなく、まだ訪問していないなら距離を更新してキューに追加する

BFS は距離が小さいマスから順に探索するため、ゴールに初めて到達した時点で、それが最短経路になります。

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N^2)\)

各マスは高々一度だけキューに入り、各マスについて上下左右の最大 \(4\) 方向を調べるため、時間計算量は \(O(N^2)\) です。

距離配列 dist とキューに最大で \(N^2\) 個のマスを保持するため、空間計算量も \(O(N^2)\) です。

実装のポイント

• Python では BFS のキューに collections.deque を使います。

  • list.pop(0) は \(O(N)\) かかるため避けます。

• グリッドの添字はコード上では \(0\) 始まりで扱っています。

• dist[sx][sy] = 1 とすることで、「通るマス数」をそのまま管理できます。

• 隣接マスに移動できる条件は次の通りです。

  • グリッドの範囲内である
  • 壁 # ではない
  • まだ訪問していない、つまり dist[nx][ny] == -1

• 到達可能であることが保証されているため、BFS 中に必ずゴールに到達できます。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    grid = [input().strip() for _ in range(N)]

    sx = sy = gx = gy = -1
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 'S':
                sx, sy = i, j
            elif grid[i][j] == 'G':
                gx, gy = i, j

    dist = [[-1] * N for _ in range(N)]
    dist[sx][sy] = 1
    q = deque([(sx, sy)])

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while q:
        x, y = q.popleft()
        if x == gx and y == gy:
            print(dist[x][y])
            return

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N:
                if grid[nx][ny] != '#' and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-xhigh によって生成されました。