概要

壁マスに入るときだけコスト（破壊回数）が \(+1\) かかる迷路で、\((1,1)\) から \((N,M)\) までの最小コストを求める問題です。各移動のコストが \(0\) または \(1\) なので、0-1 BFS で最短路を求めます。

考察

• どの経路を通っても移動回数自体は制限がなく、最小化したいのは「壊した壁の数」です。
• あるマスから隣のマスへ移動するとき、
  • 移動先が . なら追加コスト \(0\)
  • 移動先が # なら（壊して入るので）追加コスト \(1\) となります。
• つまりこの問題は、各マスを頂点、上下左右の移動を辺とみなしたときの 重み付き最短路問題です（辺の重みが \(0\) または \(1\)）。

素朴に「最短手数（移動回数）」の BFS をすると、壁を壊す回数が最小とは限りません。
例として、移動回数は短いが壁を多く壊す経路より、遠回りでも壁を壊さない経路の方が答えとして良いことがあります。

一般の重み付き最短路ならダイクストラ法ですが、この問題は重みが \(0/1\) に限られるので、ヒープを使うダイクストラ（\(O(E\log V)\)）より高速な 0-1 BFS（\(O(E)\)） が使えます。

アルゴリズム

0-1 BFS で、各マスへの「最小破壊回数」dist を求めます。

• dist[start]=0 から開始し、両端キュー deque を用意します。
• キューから頂点 \(v\) を取り出し、上下左右の隣 \(nv\) を見る。
• 追加コスト \(w\) は「移動先が壁なら \(1\)、通路なら \(0\)」：
  • w = 1 if grid[nr][nc] == '#' else 0
• もし dist[nv] > dist[v] + w なら更新し、
  • \(w=0\) のときは キューの左に入れる（優先的に処理したい）
  • \(w=1\) のときは キューの右に入れる
• これを繰り返すと、常に「現在わかっている最小コストに近い状態」から処理され、最短路が正しく求まります。

この問題では頂点数が \(NM\) と大きいので、実装ではマス \((r,c)\) を一次元の v = r*M + c に変換して配列で持つことで高速化しています。

計算量

• 時間計算量: \(O(NM)\)
  （各辺は高々定数回の更新で、0-1 BFS 全体は \(O(V+E)\)。グリッドでは \(V=NM,\ E\approx 4NM\)）
• 空間計算量: \(O(NM)\)
  （距離配列とキューなど）

実装のポイント

• 0-1 BFS：重み \(0\) の遷移は appendleft、重み \(1\) は append にするのが核心です。

• Python で \(N,M\le 500\)（最大 \(250{,}000\) マス）を扱うため、

  • グリッドは bytes で読み、'#' を 35（ord('#')）として比較

  • dist は二次元ではなく一次元配列（インデックス計算は divmod(v, M)） などの工夫で定数倍を下げています。

    ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    grid = [next(it) for _ in range(N)]  # bytes

    INF = 10**9
    size = N * M
    dist = [INF] * size

    start = 0
    goal = size - 1
    dist[start] = 0
    dq = deque([start])

    while dq:
        v = dq.popleft()
        dv = dist[v]
        r, c = divmod(v, M)

        nr = r - 1
        if nr >= 0:
            nv = v - M
            w = 1 if grid[nr][c] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

        nr = r + 1
        if nr < N:
            nv = v + M
            w = 1 if grid[nr][c] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

        nc = c - 1
        if nc >= 0:
            nv = v - 1
            w = 1 if grid[r][nc] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

        nc = c + 1
        if nc < M:
            nv = v + 1
            w = 1 if grid[r][nc] == 35 else 0
            nd = dv + w
            if nd < dist[nv]:
                dist[nv] = nd
                (dq.appendleft if w == 0 else dq.append)(nv)

    sys.stdout.write(str(dist[goal]))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。