概要

グリッド上でスタートからゴールまで移動する際に、壁を破壊する回数を最小化する問題です。通路への移動コストは \(0\)、壁への移動コストは \(1\) として最短経路を求めます。

考察

問題の本質

この問題を言い換えると、「通路を通るコストは \(0\)、壁を通るコストは \(1\) として、\((1,1)\) から \((N,M)\) への最小コスト経路を求める」問題になります。

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

ダイクストラ法を使えば解けますが、優先度付きキューを使用するため計算量が \(O(NM \log(NM))\) となり、やや重くなります。

より効率的な解法への気づき

辺の重みが \(0\) または \(1\) の2種類しかないことに注目します。このような場合、0-1 BFS という特殊なBFSを使うことで、通常のBFSと同じ \(O(NM)\) の計算量で最短経路を求められます。

アルゴリズム

0-1 BFS とは

辺の重みが \(0\) か \(1\) のみのグラフにおける最短経路問題を、deque（両端キュー）を使って効率的に解く手法です。

動作原理

通常のBFSでは距離が小さい順に頂点を処理しますが、0-1 BFSでは以下のルールで処理順序を制御します：

1. コスト \(0\) の辺で移動した場合 → dequeの先頭に追加
2. コスト \(1\) の辺で移動した場合 → dequeの末尾に追加

これにより、常に「現在の最小コストの頂点」から処理されることが保証されます。

具体例

. # .
. # .
. . .

この迷路で \((0,0)\) から \((2,2)\) への最短経路を考えます。

• 壁を破壊せずに通る経路（下→下→右→右）：コスト \(0\)
• 壁を1つ破壊して通る経路（右→下→下→右）：コスト \(1\)

0-1 BFSでは、コスト \(0\) の移動を優先的に処理するため、正しく最小コストが計算されます。

処理の流れ

1. 距離配列 dist を \(\infty\) で初期化し、dist[0][0] = 0 とする
2. dequeにスタート地点 \((0, 0)\) を追加
3. dequeが空になるまで以下を繰り返す：
   • 先頭から頂点 \((x, y)\) を取り出す
   • 隣接する4方向の各マス \((nx, ny)\) について：
     • 新しい距離が現在の距離より小さければ更新
     • 通路（コスト \(0\)）なら先頭に、壁（コスト \(1\)）なら末尾に追加

計算量

• 時間計算量: \(O(NM)\)
  • 各マスは高々1回しか最短距離で処理されないため
• 空間計算量: \(O(NM)\)
  • 距離配列とdequeの領域

実装のポイント

1. dequeの使い分け: Pythonでは collections.deque を使い、appendleft() で先頭に、append() で末尾に追加します。

2. 距離の更新条件: new_dist < dist[nx][ny] のときのみ更新することで、同じマスを何度も処理することを防ぎます。

3. 座標の扱い: 問題文では1-indexedですが、実装では0-indexedで扱うと配列アクセスが楽になります。

4. 方向ベクトル: 上下左右の4方向を配列 dx, dy で管理すると、コードがすっきりします。

   ソースコード

from collections import deque

def solve():
    N, M = map(int, input().split())
    grid = [input().strip() for _ in range(N)]
    
    # 0-1 BFS を使用
    # 通路への移動はコスト0、壁への移動はコスト1
    INF = float('inf')
    dist = [[INF] * M for _ in range(N)]
    dist[0][0] = 0
    
    # deque を使った 0-1 BFS
    dq = deque()
    dq.append((0, 0))
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    while dq:
        x, y = dq.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < M:
                # 移動先が通路ならコスト0、壁ならコスト1
                cost = 0 if grid[nx][ny] == '.' else 1
                new_dist = dist[x][y] + cost
                
                if new_dist < dist[nx][ny]:
                    dist[nx][ny] = new_dist
                    if cost == 0:
                        dq.appendleft((nx, ny))
                    else:
                        dq.append((nx, ny))
    
    print(dist[N-1][M-1])

solve()

---

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