概要

\(N \times N\) のグリッド迷路において、スタート S からゴール G までの最短経路上のマス数（両端含む）を求める問題です。典型的な 幅優先探索（BFS） で解くことができます。

考察

• 高橋君は上下左右に1マスずつ移動でき、各移動のコストは均一（1手）です。
• 辺の重みがすべて等しいグラフの最短経路問題は、BFS（幅優先探索）で効率よく解けます。
• 素朴に全経路を列挙する（DFS で全探索する）方法では、経路数が指数的に爆発し TLE になります。BFS を使えば、各マスを高々1回しか訪問しないため、効率的に最短距離を求められます。

なぜ BFS で最短経路が求まるのか？

BFS はスタートから近い順（距離 0 → 距離 1 → 距離 2 → …）にマスを探索します。あるマスに初めて到達したときの距離が、そのマスへの最短距離となります。これは辺の重みがすべて等しい場合に成り立つ重要な性質です。

具体例

5
S....
.###.
.#G#.
.#..#
.....

この例では、BFS により S(1,1) から G(3,3) への最短距離は 8 手であり、通るマスの数は \(8 + 1 = 9\) となります。

アルゴリズム

1. 入力を読み込み、S と G の座標を記録する。
2. 距離配列 dist を \(-1\)（未訪問）で初期化し、dist[sx][sy] = 0 とする。
3. キューにスタート地点を入れ、BFS を開始する。
4. キューからマス \((x, y)\) を取り出し、上下左右の隣接マス \((nx, ny)\) について：
   • グリッド範囲内かつ壁でなく、まだ未訪問なら dist[nx][ny] = dist[x][y] + 1 として、キューに追加する。
5. ゴール地点に到達したら、dist[gx][gy] + 1 を出力する（dist は移動回数＝辺の数なので、マスの数にするために \(+1\)）。

BFS の動作イメージ

スタート S からの距離:
0  1  2  3  4
1  #  #  #  5
2  #  ?  #  6
3  #  9  8  #
4  5  6  7  ...

距離が小さい順にマスを探索していくため、ゴールに最初に到達したときが最短です。

計算量

• 時間計算量: \(O(N^2)\)
  • 各マスを高々1回訪問するため、全体で最大 \(N^2\) 回の処理を行います。
• 空間計算量: \(O(N^2)\)
  • グリッドの保持と距離配列 dist、BFS のキューにそれぞれ \(O(N^2)\) の空間が必要です。

実装のポイント

• deque（両端キュー）を使う: Python の collections.deque を使うことで、キューの先頭からの取り出し（popleft）が \(O(1)\) になります。通常のリストで pop(0) を使うと \(O(N)\) かかり、TLE の原因になり得ます。

• 距離と通るマスの数の違い: dist 配列には「移動回数（辺の数）」を記録しています。問題で求められるのは「通るマスの数」なので、最終的に \(+1\) する必要があります（例: 3回移動 → 4マス通過）。

• 早期終了: ゴールに到達した時点で即座に答えを出力して終了することで、不要な探索を省略できます。

  ソースコード

from collections import deque

def main():
    N = int(input())
    grid = []
    sx = sy = gx = gy = 0
    for i in range(N):
        row = input()
        grid.append(row)
        for j in range(N):
            if row[j] == 'S':
                sx, sy = i, j
            elif row[j] == 'G':
                gx, gy = i, j

    dist = [[-1] * N for _ in range(N)]
    dist[sx][sy] = 0
    queue = deque([(sx, sy)])
    while queue:
        x, y = queue.popleft()
        if x == gx and y == gy:
            print(dist[x][y] + 1)
            return
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and grid[nx][ny] != '#' and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))

    print(dist[gx][gy] + 1)

main()

---

この解説は claude4.6opus-thinking によって生成されました。