概要

\(N \times M\) のグリッドで構成された迷路において、壁（#）を破壊する回数を最小限に抑えつつ、スタートからゴールまで移動する最短経路問題です。

考察

この問題は、グリッドをグラフとして捉えることで、最短経路問題として解くことができます。各マスを「頂点」、隣接するマスへの移動を「辺」と考えます。

移動にかかるコストを以下のように定義します： - 移動先のマスが通路（.）の場合：コスト \(0\) - 移動先のマスが壁（#）の場合：コスト \(1\) （壁を破壊して通路にするため）

このように定義すると、求める答えは「マス \((1, 1)\) からマス \((N, M)\) への最小コスト」となります。

通常の迷路（すべての移動コストが \(1\)）であれば幅優先探索（BFS）で解けますが、今回はコストが \(0\) と \(1\) の \(2\) 種類存在するため、単純なキューを用いた BFS では正しく計算できません。このような「辺の重みが \(0\) か \(1\) のみ」という特殊な状況では、0-1 BFS というアルゴリズムを用いることで、効率的に最短経路を求めることができます。

アルゴリズム

0-1 BFS

0-1 BFS は、両端キュー（deque）を利用して最短距離を求める手法です。

1. 初期化: 距離配列 dist を無限大で初期化し、スタート地点の距離を \(0\) とします。
2. 探索: deque の先頭から現在のマスを取り出し、隣接する \(4\) 方向を調べます。
3. 更新:
   • 移動先のコストが \(0\)（通路）の場合：
     • 現在の距離で更新可能なら、dist を更新し、そのマスを deque の先頭（left）に追加します。
   • 移動先のコストが \(1\)（壁）の場合：
     • 現在の距離 \(+1\) で更新可能なら、dist を更新し、そのマスを deque の末尾（right）に追加します。
4. 終了: deque が空になるか、ゴールに到達するまで繰り返します。

コスト \(0\) の移動を優先的に探索することで、ダイクストラ法を簡略化したような形で、計算量を抑えつつ最短経路を導き出せます。

計算量

• 時間計算量: \(O(N \times M)\)
  • 各マスを最大で \(1\) 回ずつ deque から取り出すため、グリッドのマス数に比例した時間で終了します。
• 空間計算量: \(O(N \times M)\)
  • グリッドの状態を保持する配列と、各マスの最短距離を保持する配列 dist にそれぞれ \(N \times M\) のメモリを使用します。

実装のポイント

• deque の活用: Python では collections.deque を使用します。コスト \(0\) のときは appendleft()、コスト \(1\) のときは append() を使い分けるのが肝心です。

• 範囲外チェック: 移動先のマスが \(0 \le r < N\) かつ \(0 \le c < M\) の範囲内に収まっているかを必ず確認します。

• 早期終了: 0-1 BFS では、あるマスが deque から取り出されたとき、そのマスへの最短距離は確定しています。そのため、ゴール地点が取り出された瞬間に答えを出力して終了することができます。

  ソースコード

import sys
from collections import deque

def solve():
    # 標準入力からすべてのデータを読み込み、空白や改行で分割します。
    # これにより、N, M およびグリッドの各行を効率的に取得できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 行数, M: 列数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # グリッドの状態を文字列のリストとして取得します
    grid = input_data[2:]
    
    # 各マスに到達するために破壊した壁の最小数を保持する2次元配列
    # 初期値として十分に大きな値（無限大）を設定します
    inf = 10**9
    dist = [[inf] * M for _ in range(N)]
    
    # スタート地点 (0, 0) のコストは 0 です
    dist[0][0] = 0
    
    # 0-1 BFS（最短経路アルゴリズムの一種）のためのデック
    # (行, 列) のタプルを格納します
    dq = deque([(0, 0)])
    
    # 移動可能な4方向（右、左、下、上）
    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
    
    while dq:
        # デックの先頭から現在のマスを取り出します
        r, c = dq.popleft()
        d = dist[r][c]
        
        # ゴール地点 (N-1, M-1) に到達した場合、その時点のコストを出力して終了します
        # 0-1 BFSでは、最初に取り出したときがそのマスへの最短経路となります
        if r == N - 1 and c == M - 1:
            print(d)
            return
        
        # 隣接する4マスを探索します
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # グリッドの範囲内であるか確認します
            if 0 <= nr < N and 0 <= nc < M:
                # 移動先のマスが壁（#）なら破壊コスト 1、通路（.）ならコスト 0
                weight = 1 if grid[nr][nc] == '#' else 0
                
                # より少ない壁破壊数でそのマスに到達できる場合、更新を行います
                if dist[nr][nc] > d + weight:
                    dist[nr][nc] = d + weight
                    
                    if weight == 0:
                        # コスト 0 の移動はデックの先頭に追加し、優先的に探索します
                        dq.appendleft((nr, nc))
                    else:
                        # コスト 1 の移動はデックの末尾に追加します
                        dq.append((nr, nc))

if __name__ == '__main__':
    solve()

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