概要

\(N \times N\) のグリッド迷路において、スタート地点 S からゴール地点 G までの最短経路に含まれるマスの数を求める問題です。

考察

この問題は、全ての移動コストが \(1\) であるグラフにおける最短経路問題とみなすことができます。

1. 最短経路の求め方: グリッド上の最短経路を求める際、深さ優先探索（DFS）では最短性が保証されず、効率も悪くなります。一方で、幅優先探索（BFS）を用いると、スタート地点に近いマスから順番に探索を進めるため、最初に見つかったゴールへの経路が必ず最短となります。
2. 「マスの数」の定義: 問題文では「経路上のマスの数（スタートとゴールを含む）」を求めています。一般的に BFS で求められる「移動回数（エッジの数）」を \(D\) とすると、通るマスの数は \(D + 1\) になります。
3. 制約の確認: \(N \leq 500\) であるため、マスの総数は \(N^2 = 250,000\) です。BFS は各マスを高々 1 回ずつしか探索しないため、計算量は \(O(N^2)\) となり、実行時間制限内に十分間に合います。

アルゴリズム

幅優先探索 (BFS) を使用します。

1. 準備:
   • 各マスの最短距離を記録する 2 次元配列 dist を用意し、未訪問であることを示す \(-1\) で初期化します。
   • 探索候補を管理するキュー（Queue）を用意し、スタート地点の座標を入れます。スタート地点の距離は dist[start] = 0 とします。
2. 探索:
   • キューが空になるまで、以下の操作を繰り返します。
     1. キューから現在のマス \((r, c)\) を取り出す。
     2. そのマスの上下左右 4 方向を調べます。
     3. 隣接するマス \((nr, nc)\) が「グリッド内にある」「壁（#）ではない」「まだ訪れていない（dist == -1）」という条件を全て満たす場合、そのマスをキューに追加し、距離を dist[nr][nc] = dist[r][c] + 1 と更新します。
3. 終了:
   • ゴール地点に到達した瞬間に、その時の距離 \(D\) に \(1\) を加えた値を出力して終了します。

計算量

• 時間計算量: \(O(N^2)\)
  • グリッドの全マスを走査してスタート・ゴールを探すのに \(O(N^2)\)、BFS で各マスを最大 1 回訪問するのに \(O(N^2)\) かかります。
• 空間計算量: \(O(N^2)\)
  • グリッドの情報および距離を保持する 2 次元配列に \(O(N^2)\) のメモリを使用します。

実装のポイント

• 効率的なキューの操作: Python では list.pop(0) は \(O(N)\) かかるため、collections.deque を使用して \(O(1)\) で要素を取り出せるようにします。

• 移動の共通化: dr = [0, 0, 1, -1], dc = [1, -1, 0, 0] のような配列を用意してループで回すことで、上下左右の移動処理を簡潔に記述できます。

• 入力の受け取り: \(N\) が大きく、迷路の各行が文字列として与えられるため、適切にパースして座標を特定する必要があります。

  ソースコード

import sys
from collections import deque

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    grid = input_data[1:]

    start_pos = None
    goal_pos = None
    
    # スタートとゴールの位置を特定
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 'S':
                start_pos = (r, c)
            elif grid[r][c] == 'G':
                goal_pos = (r, c)

    # 幅優先探索 (BFS)
    queue = deque([start_pos])
    # dist[r][c] はスタート地点からの最小移動回数
    dist = [[-1] * n for _ in range(n)]
    dist[start_pos[0]][start_pos[1]] = 0

    # 移動方向（上下左右）
    dr = [0, 0, 1, -1]
    dc = [1, -1, 0, 0]

    while queue:
        r, c = queue.popleft()

        # ゴールに到達した場合
        if (r, c) == goal_pos:
            # 経路上のマスの数は (移動回数 + 1)
            print(dist[r][c] + 1)
            return

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            
            # グリッドの範囲内かつ壁ではなく、未訪問のマスであるか確認
            if 0 <= nr < n and 0 <= nc < n:
                if grid[nr][nc] != '#' and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。