概要

この問題は、S から G まで移動するときに「P マスに入った回数」を最小化する問題です。
各移動のコストが 0（S,G,O に入る）または 1（P に入る）なので、0-1 BFS を使うと高速に最小ダメージを求められます。

考察

重要な観察は次の2つです。

1. 最小化したいのは「歩数」ではなく「P に入った回数」
   つまり、同じ長さの経路でも P の通過回数が少ない方が良いです。

2. 1回の移動で増えるダメージは 0 か 1 のどちらか

   • 移動先が P → コスト 1
   • それ以外（S,G,O）→ コスト 0
   • B はそもそも移動不可

この「辺コストが 0/1」の最短路問題は、ダイクストラでも解けますが、頂点数が最大 \(10^6\) と大きいため、より軽い 0-1 BFS が有効です。
素朴に通常 BFS（歩数最短）をすると、ダメージ最小にならないため WA になります。

また「同じマスを何度でも通れる」ので、状態は「マス位置だけ」でよく、dist[v] にそのマスへ到達する最小ダメージを持てば十分です。

アルゴリズム

1. グリッドを読み込み、S と G の位置を1次元 index（r*W+c）で管理する。
2. dist 配列を INF で初期化し、dist[S]=0。
3. deque を用いた 0-1 BFS を実行する。
   • 現在マス v から上下左右を確認
   • 壁 B は無視
   • 移動先が P なら重み w=1、それ以外は w=0
   • nd = dist[v] + w が改善なら更新
     • w=0 のとき appendleft（先頭）
     • w=1 のとき append（末尾）
4. G が deque から取り出された時点で、その dist[G] は最小なので即出力して終了。
5. 最後まで到達できなければ -1。

0-1 BFS では、コスト0遷移を先に処理することで、ダイクストラの優先度付きキュー相当の順序を deque で実現できます。

計算量

• 時間計算量: \(O(HW)\)
  （各マスにつき高々定数回の遷移緩和）
• 空間計算量: \(O(HW)\)
  （dist 配列と deque）

実装のポイント

• H \times W が大きいので、input = sys.stdin.readline を使って高速入力。

• 座標を1次元化（v = r*W+c）すると dist を1本の配列で管理できて高速。

• 重みは「入る先 が P かどうか」で決まる点に注意（現在地ではない）。

• v == g を pop 時に判定して即 return することで、余計な探索を省けます。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip() for _ in range(H)]

    s = g = -1
    for i in range(H):
        row = A[i]
        for j, ch in enumerate(row):
            if ch == 'S':
                s = i * W + j
            elif ch == 'G':
                g = i * W + j

    INF = 10**18
    N = H * W
    dist = [INF] * N
    dist[s] = 0
    dq = deque([s])

    while dq:
        v = dq.popleft()
        if v == g:
            print(dist[v])
            return

        r, c = divmod(v, W)
        base = dist[v]

        # up
        if r > 0:
            nv = v - W
            ch = A[r - 1][c]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

        # down
        if r + 1 < H:
            nv = v + W
            ch = A[r + 1][c]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

        # left
        if c > 0:
            nv = v - 1
            ch = A[r][c - 1]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

        # right
        if c + 1 < W:
            nv = v + 1
            ch = A[r][c + 1]
            if ch != 'B':
                w = 1 if ch == 'P' else 0
                nd = base + w
                if nd < dist[nv]:
                    dist[nv] = nd
                    if w == 0:
                        dq.appendleft(nv)
                    else:
                        dq.append(nv)

    print(-1)

if __name__ == "__main__":
    main()

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