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

バイナリ行列があるとします。ここで、0は空のセルを示し、1は壁を示します。最初の行の空のセルから開始して、最後の行の空のセルで終了することができます。左、右、または下に移動できます。各セルに最大で1回アクセスできる最長のパスを見つける必要があります。これが不可能な場合は、0を返します。

したがって、入力が次のような場合

（0、3）、（0、2）、（0、1）、（0、0）、（1、0）、（1、1）、（1、 2）、（2、2）、（2、1）、（2、0）。

これを解決するには、次の手順に従います-

• N：=行列の行数
• M：=行列の列数
• dp：=サイズMのリストで、-1で埋めます
• 0からN-1の範囲のiの場合、do
  • ndp：=サイズMのリストで、-1で埋めます
  • ndp2：=サイズMのリストで、-1で埋めます
  • 0〜M-1の範囲のjの場合、do
    • matrix [i、j]が1でなく、（iが0またはdp [j]> -1と同じ）の場合、
      • ndp [j]：=dp [j] + 1
      • ndp2 [j]：=dp [j] + 1
  • 1からM-1の範囲のjについては、
    • matrix [i、j]が1でなく、ndp [j-1]> -1の場合、
      • ndp [j]：=ndp [j]と（ndp [j-1] + 1）の最大値
  • M-2から0の範囲のjの場合、1ずつ減らします。
    • matrix [i、j]が1でなく、ndp2 [j + 1]> -1の場合、
      • ndp2 [j]：=ndp2 [j]および（ndp2 [j + 1] + 1）の最大値
      • ndp [j]：=ndp[j]とndp2[j]の最大値
  • dp：=ndp
• return（dpの最大値）+ 1

例

理解を深めるために、次の実装を見てみましょう-

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