概要

各マスを頂点、上下左右の移動を辺とみなすと、この問題は「S から G までの最小コスト経路」を求める問題です。
移動先が P のときだけコスト \(1\)、それ以外はコスト \(0\) なので、0-1 BFS を使うと高速に解けます。

考察

この問題で最小化したいのは「移動回数」ではなく、P に入った回数です。

たとえば、

• 5歩で P を 2 回踏む経路
• 8歩で P を 0 回しか踏まない経路

があったとき、答えは後者です。
したがって、普通の BFS のように「最短手数」を求めても正しい答えにはなりません。

---

各移動について、コストを次のように考えます。

• 移動先が P：コスト \(1\)
• 移動先が S, G, O：コスト \(0\)
• B には移動できない

すると、問題は

重みが \(0\) または \(1\) の辺だけからなるグラフで、始点 S から終点 G までの最短距離を求める

問題に言い換えられます。

---

なぜ Dijkstra ではなく 0-1 BFS なのか

もちろん Dijkstra 法でも解けます。
しかしこの問題では辺の重みが \(0\) と \(1\) の2種類しかないため、0-1 BFS を使うともっと軽く実装でき、計算量も \(O(V+E)\) になります。

制約は \(H \times W \leq 10^6\) とかなり大きいので、Python では \(O(E \log V)\) の Dijkstra よりも 0-1 BFS の方が安全です。

---

0-1 BFS の考え方

通常の BFS ではキューを使いますが、0-1 BFS では deque（両端キュー） を使います。

現在位置から隣に移動するとき、

• コスト \(0\) の移動なら appendleft
• コスト \(1\) の移動なら append

とします。

こうすると、deque から取り出す順番が「距離の小さい順」に保たれ、Dijkstra 法と同じように最短距離を求められます。

---

例

たとえば、あるマスから隣接マスへ行くとき

• O へ行く → ダメージ増加なし → コスト \(0\)
• P へ行く → ダメージ \(1\) 増加 → コスト \(1\)

なので、O や G に進む候補は deque の前に入れ、P に進む候補は後ろに入れます。

これにより、「ダメージが少ない経路」が優先的に探索されます。

アルゴリズム

1. 迷路を 1 次元配列として持つ。
2. 外周をすべて B で埋めた番兵付きの配列を作る。
   • こうすると上下左右移動のたびに範囲チェックを書かなくてよい。
3. dist[v] を「S からマス v に到達する最小ダメージ」とする。
4. dist[start] = 0 として 0-1 BFS を行う。
5. 現在位置 v から上下左右の隣 nv を見る。
   • B ならスキップ
   • それ以外なら
     $\( nd = dist[v] + \begin{cases} 1 & (\text{移動先が } P) \\ 0 & (\text{それ以外}) \end{cases} \)$
6. nd < dist[nv] なら更新する。
   • P なら deque の後ろへ
   • それ以外なら deque の前へ
7. G が取り出された時点で、その距離が最小なので答えを出力する。
8. 最後まで到達できなければ -1 を出力する。

---

なぜこれで正しいか

各移動のコストは「移動先が P かどうか」で決まり、必ず \(0\) または \(1\) です。
したがって、この問題は 0-1 BFS がそのまま適用できる最短路問題です。

また、0-1 BFS では deque から取り出した頂点は、その時点で最小の距離が確定しています。
よって G を取り出した瞬間の dist[G] が、求める最小累積ダメージです。

計算量

• 時間計算量: \(O(HW)\)
• 空間計算量: \(O(HW)\)

※ 各マスを頂点とすると頂点数は \(O(HW)\)、各頂点からの辺は高々 4 本なので、辺数も \(O(HW)\) です。
0-1 BFS は \(O(V+E)\) なので全体で \(O(HW)\) になります。

実装のポイント

• 番兵付き配列を使って、迷路の外周をすべて B にしてあります。
  これにより、毎回 0 <= ni < H のような範囲チェックが不要になります。
• 2 次元配列ではなく 1 次元配列 にしており、隣接マスは
  • 左: -1
  • 右: +1
  • 上: -PW
  • 下: +PW

で表せます。 - 文字列比較を高速化するため、盤面を bytearray として持ち、B や P も文字コードで比較しています。 - 0-1 BFS では同じ頂点が deque に複数回入ることがあるため、done 配列で「確定済みか」を管理しています。これにより無駄な処理を減らせます。

ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.buffer.readline

    H, W = map(int, input().split())
    PW = W + 2
    PH = H + 2
    N = PW * PH

    B = ord('B')
    P = ord('P')

    grid = bytearray([B]) * N
    start = -1
    goal = -1

    for i in range(H):
        row = input().strip()
        base = (i + 1) * PW + 1
        grid[base:base + W] = row

        j = row.find(b'S')
        if j != -1:
            start = base + j

        j = row.find(b'G')
        if j != -1:
            goal = base + j

    INF = 10**18
    dist = [INF] * N
    done = bytearray(N)

    dq = deque([start])
    dist[start] = 0

    offsets = (-1, 1, -PW, PW)

    while dq:
        v = dq.popleft()
        if done[v]:
            continue
        done[v] = 1

        if v == goal:
            print(dist[v])
            return

        dv = dist[v]
        for off in offsets:
            nv = v + off
            ch = grid[nv]
            if ch == B:
                continue

            nd = dv + (ch == P)
            if nd < dist[nv]:
                dist[nv] = nd
                if ch == P:
                    dq.append(nv)
                else:
                    dq.appendleft(nv)

    print(-1)

if __name__ == "__main__":
    main()

---

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