Pythonで最長のマトリックスパスの長さを求めるプログラム

問題の概要

0が空きセル、1が壁を表すバイナリ行列(マトリックス)を考えます。最初の行の任意の空きセルからスタートし、最後の行の任意の空きセルに到達することを目指します。移動できるのは「左」「右」「下」の3方向のみで、各セルは最大1回しか訪れることができません。この条件のもとで、最も長いパスの長さを求める必要があります。到達が不可能な場合は0を返します。

例えば、入力が以下のような行列だったとします。

この場合の出力は10です。(0, 3) → (0, 2) → (0, 1) → (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2) → (2, 1) → (2, 0) の順に移動することで、合計10個のセルを訪問できるためです。

解決アプローチ:動的計画法(DP)

この問題は動的計画法を用いることで効率的に解けます。各行ごとに「その行の各列に到達した時点での最長パス長」を記録していきます。同じ行の中で左右どちらからでも移動できるため、左方向と右方向の伝播を別々に管理する2つのDPテーブル(ndp と ndp2)を用意するのがポイントです。-1 は「そのセルに到達不可能」であることを表します。

アルゴリズムの手順

• N := 行列の行数、M := 列数とします。
• dp := サイズMのリストを作成し、すべて-1で初期化します。
• i を 0 から N-1 まで繰り返します。
  • ndp と ndp2 := それぞれサイズMのリストを作成し、-1で初期化します。
  • j を 0 から M-1 まで走査し、matrix[i][j] が壁でなく、かつ(iが0行目である、またはdp[j]が到達可能な)場合、ndp[j] と ndp2[j] を dp[j] + 1 に設定します。
  • j を 1 から M-1 まで左から右へ走査し、matrix[i][j] が壁でなく ndp[j-1] が到達可能なら、ndp[j] を max(ndp[j], ndp[j-1] + 1) で更新します。
  • j を M-2 から 0 まで右から左へ走査し、matrix[i][j] が壁でなく ndp2[j+1] が到達可能なら、ndp2[j] を max(ndp2[j], ndp2[j+1] + 1) で更新し、さらに ndp[j] を max(ndp[j], ndp2[j]) で更新します。
  • dp := ndp とします。
• 最後に max(dp) + 1 を返します(+1は開始セル分のカウントです)。

この手法では各セルを定数回だけ処理するため、計算量はO(N×M)となり、全経路を探索する指数時間のアプローチよりも大幅に高速です。

実装例

理解を深めるために、以下のPythonコードをご覧ください。

def solve(matrix):
   N = len(matrix)
   M = len(matrix[0])
   dp = [-1 for i in matrix[0]]
   for i in range(N):
      ndp = [-1 for j in matrix[0]]
      ndp2 = [-1 for j in matrix[0]]
      for j in range(M):
         if matrix[i][j] != 1 and (i == 0 or dp[j] > -1):
            ndp[j] = dp[j] + 1
            ndp2[j] = dp[j] + 1

      for j in range(1, M):
         if matrix[i][j] != 1 and ndp[j - 1] > -1:
            ndp[j] = max(ndp[j], ndp[j - 1] + 1)

      for j in range(M - 2, -1, -1):
         if matrix[i][j] != 1 and ndp2[j + 1] > -1:
            ndp2[j] = max(ndp2[j], ndp2[j + 1] + 1)
            ndp[j] = max(ndp[j], ndp2[j])

      dp = ndp
   return max(dp) + 1

matrix = [
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
print(solve(matrix))

入力

[
[0, 0, 0, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
]

出力

10