概要

\(H \times W\) のグリッド上を、ある区画に入るときにその区画の通行料を支払うというルールのもと、左上 \((1, 1)\) から右下 \((H, W)\) まで移動したときに支払う通行料の合計の最小値を求める問題です。

考察

グラフ問題への帰着

この問題は、各マスを「頂点」、上下左右に隣接するマスへの移動を「有向辺」とみなした最短経路問題として捉えることができます。

ある区画から区画 \((r, c)\) へ移動するたびに通行料 \(A_{r, c}\) が発生するため、区画 \((r, c)\) へ向かうすべての有向辺の重みを \(A_{r, c}\) と設定します。 スタート地点 \((1, 1)\) に最初にいるときの通行料は支払わないため、初期状態（移動距離 \(0\)）でのコストは \(0\) となります。

なぜ単純な動的計画法（DP）では解けないか

「左上から右下への移動」と聞くと動的計画法（DP）を思い浮かべがちですが、本問では上下左右の \(4\) 方向すべてに移動可能です。 例えば、直接右へ進むマスの通行料が極めて大きい場合、一度上や下に迂回した方が結果的に安くなるケースが考えられます。移動にループや後戻りが含まれうるため、マスの訪問順序を一方向に限定する単純なDPでは解けません。

ダイクストラ法の適用

すべての通行料 \(A_{i, j}\) は \(0\) 以上であるため、辺の重みは非負です。 負の重みの辺が存在しない単一始点最短経路問題は、ダイクストラ法（Dijkstra’s algorithm） を用いて効率的に解くことができます。

アルゴリズム

優先度付きキュー（ヒープ）を用いたダイクストラ法を適用します。

1. 頂点の一次元化: \(H \times W\) 個のマス \((i, j)\)（\(0\)-indexed）を、単一の整数インデックス \(u = i \times W + j\) で管理します。
2. 初期化:
   • スタート地点から各マスへの最小コストを記録する配列 dist を用意し、すべて十分大きな値（\(\infty\)）で初期化します。
   • スタート地点 \(u = 0\)（マス \((0, 0)\)）のコストを \(0\) とし、優先度付きキューに (コスト 0, 頂点 0) を追加します。
3. 探索:
   • 優先度付きキューから「暫定コストが最小の頂点 \(u\)」を取り出します。
   • キューから取り出したコストがすでに記録されている dist[u] より大きい場合は無視します。
   • \(u\) が目的地の頂点（\(H \times W - 1\)）であれば、そのときのコストが最小値として確定しているため探索を終了し、コストを出力します。
   • \(u\) に上下左右で隣接するマス \(v\) について、頂点 \(v\) に入るコスト \(A_v\) を加えた新たなコスト \(d + A_v\) が現在の dist[v] より小さければ、dist[v] を更新して優先度付きキューに追加します。

計算量

• 時間計算量: \(O(HW \log(HW))\)
  • 頂点数は \(V = H \times W\)、各頂点から出る辺の数は最大 \(4\) 本なので辺数は \(E \le 4HW\) です。
  • ダイクストラ法の時間計算量は \(O(E \log V)\) であるため、全体で \(O(HW \log(HW))\) となります。
  • 制約より \(HW \le 2 \times 10^5\) であるため、計算ステップ数は約 \(3.6 \times 10^6\) 回程度であり、実行時間制限に十分間に合います。
• 空間計算量: \(O(HW)\)
  • 通行料を保持する配列、最短距離配列 dist、優先度付きキューで \(O(HW)\) のメモリを使用します。

実装のポイント

• グリッドの一次元化と境界判定: マスのインデックスを \(u\) としたとき、\(u \pmod W\) を確認することで左右の移動可否を判定できます。

  • 上への移動: \(u \ge W\) のとき可能（移動先: \(u - W\)）
  • 下への移動: \(u < HW - W\) のとき可能（移動先: \(u + W\)）
  • 左への移動: \(u \pmod W \neq 0\) のとき可能（移動先: \(u - 1\)）
  • 右への移動: \(u \pmod W \neq W - 1\) のとき可能（移動先: \(u + 1\)）

• 高速な入出力: 入力サイズが大きいため（最大 \(2 \times 10^5\) 個以上の整数）、Python では sys.stdin.read().split() を用いて一度に入力を読み込むことで入出力による実行時間を大幅に削減できます。

• ゴール到達時の早期終了: ダイクストラ法では、ヒープから目的地の頂点を取り出した瞬間にその頂点への最短経路が確定するため、その時点で処理を終了して結果を出力することで無駄な計算を省くことができます。

  ソースコード

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    H = int(input_data[0])
    W = int(input_data[1])
    
    A = [int(x) for x in input_data[2:]]
    
    total_nodes = H * W
    INF = 10**18
    dist = [INF] * total_nodes
    dist[0] = 0
    
    pq = [(0, 0)]
    target = total_nodes - 1
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
        
        if u == target:
            print(d)
            return
            
        mod = u % W
        
        # 上
        if u >= W:
            v = u - W
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
        # 下
        if u < total_nodes - W:
            v = u + W
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
        # 左
        if mod != 0:
            v = u - 1
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
        # 右
        if mod != W - 1:
            v = u + 1
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

if __name__ == '__main__':
    solve()

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