Python程式：查詢矩陣中最長路徑長度

假設我們有一個二進位制矩陣，其中0表示空單元格，1表示牆壁。我們可以在第一行的任何空單元格開始，並希望在最後一行的任何空單元格結束。我們可以向左、向右或向下移動，我們必須找到最長的路徑，其中每個單元格最多隻能訪問一次。如果這是不可能的，則返回0。

因此，如果輸入如下所示：

則輸出將為10，因為我們可以移動(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
• 對於i從0到N-1迴圈：
  • ndp := 一個大小為M的列表，並填充-1
  • ndp2 := 一個大小為M的列表，並填充-1
  • 對於j從0到M-1迴圈：
    • 如果matrix[i, j]不等於1並且(i等於0或dp[j] > -1)，則
      • ndp[j] := dp[j] + 1
      • ndp2[j] := dp[j] + 1
  • 對於j從1到M-1迴圈：
    • 如果matrix[i, j]不等於1並且ndp[j - 1] > -1，則
      • ndp[j] := ndp[j]和(ndp[j - 1] + 1)中的最大值
  • 對於j從M-2到0遞減迴圈：
    • 如果matrix[i, j]不等於1並且ndp2[j + 1] > -1，則
      • ndp2[j] := ndp2[j]和(ndp2[j + 1] + 1)中的最大值
      • ndp[j] := ndp[j]和ndp2[j]中的最大值
  • dp := ndp
• 返回(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

Arnab Chakraborty

更新於：2021年10月19日

211 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習