Pythonで最小限の労力でパスを見つけるプログラム

問題の概要

m × n の2次元行列 heights が与えられます。heights[i][j] はセル (i, j) の高さを表します。現在セル (0, 0) にいて、右下のセル (m-1, n-1) まで移動したいとします。移動は上下左右の4方向が可能で、「労力」が最小になるような経路を見つけることが目的です。

ここでいう「労力」とは、経路上で隣り合う2つのセル間の高さの絶対差のうち、最大値のことです。つまり、目的地に到達するために必要な最小の労力を求める必要があります。

入力例

この場合の出力は 1 になります。経路 [2, 3, 4, 5, 6] を通ると、隣接セル間の高さの絶対差の最大値が 1 となるためです。

解法のアプローチ

この問題は、ダイクストラ法(Dijkstra法)の考え方を応用することで効率的に解けます。通常のダイクストラ法は辺のコストの「合計」を最小化しますが、この問題では「経路上の最大コスト」を最小化する点が異なります。優先度付きキュー(heapq)を使い、常にこれまでの労力が最も小さいセルから探索を進めることで、目的地に到達した時点の労力が最小であることが保証されます。

アルゴリズムの手順

• r := 行数、c := 列数 とする
• queue := 優先度付きキューを用意し、初期値としてタプル (0, 0, 0) を格納する
• キューが空でない間、以下を繰り返す:
  • cur := キューから先頭(最小の要素)を取り出す
  • c_eff := cur[0](現在の労力)、x := cur[1]、y := cur[2](現在位置)
  • x == r-1 かつ y == c-1(目的地に到達)なら、c_eff を返す
  • heights[x][y] が空文字列(訪問済み)なら、次の反復へスキップ
  • [1,0], [-1,0], [0,1], [0,-1] の各方向 (dx, dy) について:
    • newx := x + dx、newy := y + dy
    • 0 <= newx < r かつ 0 <= newy < c かつ heights[newx][newy] が空文字列でない場合:
      • eff := max(c_eff, |heights[newx][newy] − heights[x][y]|)
      • タプル (eff, newx, newy) をキューに挿入
  • heights[x][y] := ""(訪問済みとしてマーク)

Pythonによる実装例

以下の実装を見ると、理解がより深まるでしょう。

import heapq

def solve(heights):
    r, c = len(heights), len(heights[0])
    queue = [(0, 0, 0)]

    while queue:
        cur = heapq.heappop(queue)
        c_eff = cur[0]
        x = cur[1]
        y = cur[2]

        if x == r - 1 and y == c - 1:
            return c_eff

        if heights[x][y] == "":
            continue

        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            newx = x + dx
            newy = y + dy
            if 0 <= newx < r and 0 <= newy < c and heights[newx][newy] != "":
                eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
                heapq.heappush(queue, (eff, newx, newy))

        heights[x][y] = ""

matrix = [[2, 3, 4], [4, 9, 5], [6, 4, 6]]
print(solve(matrix))

入力

[[2,3,4],[4,9,5],[6,4,6]]

出力

1

まとめ

このように、優先度付きキューを活用したダイクストラ法風のアプローチにより、グリッド上の移動コスト(隣接セル間の高さ差の最大値)を最小化する経路を効率的に求められます。計算量は O(mn・log(mn)) となり、比較的大きなグリッドでも実用的な速度で動作します。訪問済みセルの管理には、ここでは配列の値を空文字列で上書きする手法を使っていますが、実務では visited 用の2次元配列を別途用意する方が可読性や保守性の面で推奨されます。