概要

迷路上で開始地点 S からゴール G まで移動する際、罠マス P を踏む回数（累積ダメージ）を最小化する問題です。辺の重みが 0 または 1 のみの最短経路問題に帰着でき、0-1 BFS で効率的に解けます。

考察

重要な気づき

この問題では、隣接マスへの移動コストが次の2種類しかありません。

• 移動先が S, G, O のマス → コスト 0（ダメージなし）
• 移動先が P のマス → コスト 1（ダメージ +1）
• 移動先が B のマス → 移動不可

つまり、マス目をグラフとみなすと、辺の重みが 0 か 1 のグラフ上での最短経路問題になります。

素朴なアプローチの問題点

ダイクストラ法（優先度付きキュー）を使えば解けますが、優先度付きキューの操作に \(O(\log N)\) のコストがかかります。\(H \times W\) が最大 \(10^6\) と大きいため、Python では定数倍の重さも相まって厳しくなる可能性があります。

解決策：0-1 BFS

辺の重みが 0 と 1 の2種類しかない場合、0-1 BFS という手法が使えます。通常の BFS では FIFO のキュー（deque）を使いますが、0-1 BFS では次のルールでキューに追加します。

• コスト 0 の辺で遷移 → キューの先頭に追加（appendleft）
• コスト 1 の辺で遷移 → キューの末尾に追加（append）

こうすることで、キューの中身が常にコスト順にソートされた状態を保てるため、優先度付きキューを使わずに最短距離が正しく求まります。

アルゴリズム

1. 入力を読み込み、S と G の位置を記録する。
2. 距離配列 dist[i][j] を \(\infty\) で初期化し、dist[sx][sy] = 0 とする。
3. 両端キュー（deque）に開始地点を入れる。
4. キューが空になるまで以下を繰り返す：
   • キューの先頭から座標 \((x, y)\) を取り出す。
   • \((x, y)\) がゴールなら dist[x][y] を出力して終了。
   • 上下左右の隣接マス \((nx, ny)\) を調べる：
     • 範囲外または B ならスキップ。
     • 移動コスト \(c\) を計算（P なら 1、それ以外は 0）。
     • dist[x][y] + c < dist[nx][ny] なら距離を更新し、\(c = 0\) ならキュー先頭へ、\(c = 1\) ならキュー末尾へ追加。
5. ゴールに到達できなかった場合は -1 を出力する。

具体例

3 3
S O P
O B P
O O G

S(0,0) → (1,0) → (2,0) → (2,1) → (2,2) = G と進めばコスト 0 で到達でき、罠 P を一度も踏みません。一方、S(0,0) → (0,2) → (1,2) → (2,2) = G だと P を2回踏むのでコスト 2 です。0-1 BFS はコスト 0 の遷移を優先的に処理するため、最小コストの経路が先に見つかります。

計算量

• 時間計算量: \(O(H \times W)\)
  • 各マスはキューに高々定数回しか追加されず、各マスから最大4方向を調べるため。
• 空間計算量: \(O(H \times W)\)
  • 距離配列とキューの分。

実装のポイント

• deque の使い分けが 0-1 BFS の核心です。コスト 0 の遷移は appendleft、コスト 1 の遷移は append を忘れないようにしましょう。

• ゴールをキューから取り出した時点で即座に答えを出力して終了できます。0-1 BFS ではキューから取り出した時点でその頂点の最短距離が確定しているためです。

• Python では sys.stdin.buffer.read() で入力を一括読み込みすると高速化できます。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    H = int(tokens[idx]); idx += 1
    W = int(tokens[idx]); idx += 1
    
    grid = []
    sx = sy = gx = gy = 0
    for i in range(H):
        row = tokens[idx]; idx += 1
        grid.append(row)
        for j in range(len(row)):
            if row[j] == 'S':
                sx, sy = i, j
            elif row[j] == 'G':
                gx, gy = i, j
    
    # 0-1 BFS: cost 0 for S/G/O, cost 1 for P, B is wall
    INF = float('inf')
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    dq = deque()
    dq.append((sx, sy))
    
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    
    while dq:
        x, y = dq.popleft()
        d = dist[x][y]
        if x == gx and y == gy:
            print(d)
            return
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W:
                c = grid[nx][ny]
                if c == 'B':
                    continue
                nd = d + (1 if c == 'P' else 0)
                if nd < dist[nx][ny]:
                    dist[nx][ny] = nd
                    if c == 'P':
                        dq.append((nx, ny))
                    else:
                        dq.appendleft((nx, ny))
    
    print(dist[gx][gy] if dist[gx][gy] < INF else -1)

main()

---

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