概要

この問題は、重みのないグリッド上で S から G までの最短経路を求める問題です。
上下左右に1マスずつ動けるので、幅優先探索（BFS）を使えば最短で通るマス数を効率よく求められます。

考察

重要なポイントは、各移動のコストがすべて同じ（1手）であることです。
このような「辺の重みがすべて同じ」最短路問題は BFS が最適です。

まず素朴に「すべての経路を試す」DFS（深さ優先探索）をすると、分岐が多い迷路では経路数が爆発し、\(N \le 500\) では到底間に合いません。
また、DFSだと最初に見つかった経路が最短とは限らず、最短保証のためには大量の探索が必要になります。

一方 BFS は、スタートから距離 1、距離 2、距離 3… の順に探索します。
したがって、あるマスに初めて到達した時点の距離が最短距離です。
この性質を使えば、G に到達した瞬間の値が答えになります。

この問題では「手数」ではなく「経路上のマス数（S,G 含む）」を出す必要があります。
そこで実装では dist[S] = 1 として開始し、隣接マスへは +1 していくことで、そのまま「通過マス数」を管理しています。

アルゴリズム

1. 入力を受け取り、グリッド内の S と G の座標を見つける。
   
2. dist 配列（未訪問は -1）を用意する。
   
3. キュー deque を使って BFS を行う。
   
   • 初期状態: S をキューに入れ、dist[S] = 1
     
4. キューから (x, y) を取り出し、4方向（上下左右）を確認する。
   
   • グリッド内である
     
   • 壁 # ではない
     
   • まだ未訪問（dist == -1）
     を満たすマス (nx, ny) に対して、dist[nx][ny] = dist[x][y] + 1 としてキューに追加。
     
5. 取り出したマスが G なら、その dist を出力して終了。
   （BFSなのでこの値が最小）

計算量

• 時間計算量: \(O(N^2)\)
  各マスを高々1回ずつキューに入れ、各回で最大4方向を見るため。
• 空間計算量: \(O(N^2)\)
  dist 配列とキューで最大 \(N^2\) マスを保持する可能性があるため。

実装のポイント

• この問題の答えは「移動回数」ではなく「通るマス数」なので、dist[S]=1 にするのが重要です。
  もし dist[S]=0 にすると、最後に +1 する補正が必要になります。

• 訪問管理は dist[nx][ny] == -1 で一元化するとシンプルです（別の visited 配列が不要）。

• N=500 では入力が大きいので、sys.stdin.readline を使うと安定して高速です。

  ソースコード

import sys
from collections import deque

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

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

    dist = [[-1] * N for _ in range(N)]
    q = deque()
    q.append((sx, sy))
    dist[sx][sy] = 1  # マス数として数えるため開始を1にする

    dirs = [(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
        nd = dist[x][y] + 1
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < N and dist[nx][ny] == -1 and grid[nx][ny] != '#':
                dist[nx][ny] = nd
                q.append((nx, ny))

if __name__ == "__main__":
    main()

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