概要

グリッド上の迷路において、スタート地点からゴール地点まで移動する際に破壊しなければならない壁の数を最小化する問題。

考察

この問題では、単にスタートからゴールまで到達する経路を見つけるだけでなく、「どの壁を破壊するか」によって「破壊回数の少ない経路」を選ぶ必要があります。

素朴な方法として、幅優先探索（BFS）を思いつくかもしれませんが、これは「移動回数」を最小にするアルゴリズムであり、今回の目的である「壁の破壊回数」を最小にするには適していません。例えば、移動回数は少なくても壁をたくさん破壊する必要がある経路が最適でない可能性があります。

そこで考えたいのが、「各マスに到達するまでの最小の壁破壊回数」を管理しながら探索する方法です。これは重み付きグラフにおける最短距離を求める問題と捉えることができ、ダイクストラ法が有効です。

具体的には： - 各マスをグラフの頂点と考える。 - 隣接マスへの移動を辺とし、移動先が通路ならコスト0、壁ならコスト1とする。 - このようにコストを設定することで、ダイクストラ法により「スタートからゴールまでの最小コスト（＝最小壁破壊回数）」を求めることができる。

アルゴリズム

この問題は、グリッドをグラフとみなした上で、ダイクストラ法を用いて最短経路（＝最小壁破壊回数）を求めることで解けます。

手順

1. 各マス \((i, j)\) に対して、そこまでの最小コスト（壁の破壊回数）を記録する二次元配列 dist を用意し、初期値を無限大に設定する。
2. スタート地点 \((0, 0)\) のコストを 0 とし、優先度付きキュー（ヒープ）に \((0, 0, 0)\) を追加する。
3. キューからコストが最小のマスを取り出し、隣接する上下左右のマスに移動を試みる。
4. 移動先が：
   • 通路ならコスト0で移動。
   • 壁ならコスト1で移動（破壊する）。
5. 移動後のコストが、すでに記録されているコストよりも小さければ、更新してキューに追加。
6. ゴール \((N-1, M-1)\) に到達した時点で、その時点でのコストが答えとなる。

このように、移動コストが0または1である点を利用して、ダイクストラ法で最短経路を求めます。

計算量

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

ここで、\(N, M\) はそれぞれグリッドの行数と列数です。ダイクストラ法では優先度付きキューの操作に \(\log\) がかかるため、全体で上記のような計算量になります。

実装のポイント

• グリッドのサイズが最大 \(500 \times 500\) なので、計算量的にもダイクストラ法が間に合う。

• 各マスのコストを dist という二次元配列で管理し、初期値は float('inf') にしておく。

• 優先度付きキューには (cost, row, col) のタプルを入れ、コストの小さい順に取り出す。

• 移動先が壁かどうかでコストを 0 または 1 に変える処理が肝心。

• 同じマスを複数回キューに入れる可能性があるので、dist[x][y] < cost の場合はスキップする処理が必要。

  ソースコード

import heapq
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    S = data[2:2+N]
    
    # グリッドのコストを管理する二次元配列
    dist = [[float('inf')] * M for _ in range(N)]
    dist[0][0] = 0
    
    # ダイクストラ法用の優先度付きキュー
    queue = [(0, 0, 0)]  # (cost, row, col)
    
    # 移動方向（上下左右）
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        cost, x, y = heapq.heappop(queue)
        
        # 現在のコストが既に記録されているコストより大きい場合はスキップ
        if cost > dist[x][y]:
            continue
        
        # 各方向への移動を試す
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # グリッド範囲外のチェック
            if 0 <= nx < N and 0 <= ny < M:
                # 壁ならコスト1、通路ならコスト0
                new_cost = cost + (1 if S[nx][ny] == '#' else 0)
                
                # 新しいコストが現在の記録より小さければ更新してキューに追加
                if new_cost < dist[nx][ny]:
                    dist[nx][ny] = new_cost
                    heapq.heappush(queue, (new_cost, nx, ny))
    
    # 右下のマスまでの最小コストを出力
    print(dist[N-1][M-1])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。