概要

\(H \times W\) のグリッドで構成された迷路において、開始地点 S からゴール G までの最小ダメージを求める最短経路問題です。通常マスを通る際のコストは \(0\)、罠マス P を通る際のコストは \(1\) と考えることができます。

考察

この問題のポイントは、「移動回数（歩数）」ではなく「累積ダメージ」を最小化するという点です。

通常の幅優先探索（BFS）は、すべての移動コストが等しい（例えばすべて \(1\)）場合に最短距離を求めるのに適しています。しかし、本題では移動先のマスの種類によってコストが \(0\)（S, G, O）または \(1\)（P）と異なります。

このような「コストが \(0\) か \(1\) のいずれか」であるグラフの最短経路問題は、0-1 BFS という手法を用いることで、通常のダイクストラ法 \(O(E \log V)\) よりも高速な \(O(V + E)\) で解くことができます。

アルゴリズム

0-1 BFS

両端キュー（deque）を利用して、現在の累積ダメージが小さい順に探索を進めます。

1. 開始地点 S のダメージを \(0\) とし、それ以外を無限大（\(\infty\)）に初期化します。
2. S を deque に追加します。
3. deque が空になるまで、以下の操作を繰り返します：
   • deque の先頭から現在のマス \(u\) を取り出す。
   • すでにそのマスの最小ダメージが確定している（訪問済み）ならスキップする。
   • 隣接する 4 方向のマス \(v\) について：
     • \(v\) が壁 B でなく、かつ \(v\) への新しいダメージが現在の記録より小さい場合：
       • 移動先が罠マス P（コスト 1）の場合： ダメージを \(+1\) し、v を deque の後ろ（back）に追加する。
       • 移動先がそれ以外（コスト 0）の場合： ダメージはそのまま（\(+0\)）で、v を deque の先頭（front）に追加する。

このように、コスト \(0\) の移動を優先的に探索（キューの先頭に追加）することで、常にダメージが最小の経路から順に探索を進めることができます。

計算量

マスの総数を \(N = H \times W\) とします。

• 時間計算量: \(O(H \times W)\) 各マスを最大 1 回ずつ訪問し、各マスから 4 方向を調べるため、グリッドのサイズに対して線形時間で動作します。
• 空間計算量: \(O(H \times W)\) グリッド情報の保持、および各マスの最小ダメージを記録する配列に \(O(H \times W)\) のメモリを使用します。

実装のポイント

• グリッドの平坦化: 2次元配列（リストのリスト）として扱うよりも、1次元の文字列やリストとして扱う方が Python では高速に動作する場合があります。本コードでは grid = "".join(input_data[2:]) により 1 次元化しています。

• 効率的な入出力: \(H \times W \leq 10^6\) と入力サイズが大きいため、sys.stdin.read().split() を用いて一括で読み込むことで、実行時間を短縮しています。

• 訪問済み管理: 0-1 BFS では、同じマスが複数回 deque に追加される可能性があるため、取り出した際に processed フラグなどで確定済みかどうかを判定すると効率的です。

  ソースコード

import sys
from collections import deque

def solve():
    # Read all input at once and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # H: number of rows, W: number of columns
    H = int(input_data[0])
    W = int(input_data[1])
    
    # Concatenate all rows into a single string for faster indexing
    # Since H * W <= 10^6, this is efficient in Python.
    grid = "".join(input_data[2:])
    
    # Find the indices of start 'S' and goal 'G' in the flattened grid
    start_idx = grid.find('S')
    goal_idx = grid.find('G')
    
    # Distance array initialized with a value larger than any possible damage
    # H * W is a safe upper bound for cumulative damage.
    INF = H * W + 1
    dist = [INF] * (H * W)
    dist[start_idx] = 0
    
    # Array to track whether a cell's neighbors have already been processed
    # In 0-1 BFS, the first time a node is popped, its distance is minimal.
    processed = [False] * (H * W)
    
    # Deque for 0-1 BFS
    dq = deque([start_idx])
    popleft = dq.popleft
    appendleft = dq.appendleft
    append = dq.append
    
    while dq:
        u = popleft()
        
        # If this cell has already been processed, skip it
        if processed[u]:
            continue
        processed[u] = True
        
        # Current cumulative damage to reach cell u
        d = dist[u]
        
        # If we reached the goal, output the minimal damage and exit
        if u == goal_idx:
            print(d)
            return
        
        # Determine current row and column for boundary checks
        r, c = divmod(u, W)
        
        # Explore neighbors in four directions: Up, Down, Left, Right
        
        # Up
        if r > 0:
            v = u - W
            char_v = grid[v]
            if char_v != 'B':
                if char_v == 'P':
                    # Cost 1 for entering a trapマス 'P'
                    if dist[v] > d + 1:
                        dist[v] = d + 1
                        append(v)
                else:
                    # Cost 0 for entering 'S', 'G', or 'O'
                    if dist[v] > d:
                        dist[v] = d
                        appendleft(v)
        
        # Down
        if r < H - 1:
            v = u + W
            char_v = grid[v]
            if char_v != 'B':
                if char_v == 'P':
                    if dist[v] > d + 1:
                        dist[v] = d + 1
                        append(v)
                else:
                    if dist[v] > d:
                        dist[v] = d
                        appendleft(v)
        
        # Left
        if c > 0:
            v = u - 1
            char_v = grid[v]
            if char_v != 'B':
                if char_v == 'P':
                    if dist[v] > d + 1:
                        dist[v] = d + 1
                        append(v)
                else:
                    if dist[v] > d:
                        dist[v] = d
                        appendleft(v)
        
        # Right
        if c < W - 1:
            v = u + 1
            char_v = grid[v]
            if char_v != 'B':
                if char_v == 'P':
                    if dist[v] > d + 1:
                        dist[v] = d + 1
                        append(v)
                else:
                    if dist[v] > d:
                        dist[v] = d
                        appendleft(v)
                        
    # If the goal 'G' is not reachable from 'S'
    print("-1")

if __name__ == '__main__':
    solve()

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