Python程式：查詢從左上角到右下角的路徑數

假設我們有一個N x M的二進位制矩陣。其中0表示空單元格，1表示阻塞單元格。現在從左上角開始，我們必須找到到達右下角的方法數量。如果答案非常大，則將其模10^9 + 7。

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

0	0	1
0	0	0
1	1	0

則輸出為2，因為到達右下角有兩種方法：[右，下，右，下]和[下，右，右，下]。

為了解決這個問題，我們將遵循以下步驟：

dp := 與給定矩陣大小相同的矩陣，並填充0
dp[0, 0] := 1
對於範圍從1到矩陣行數的i，執行：
- 如果matrix[i, 0]等於1，則
  - 退出迴圈
- 否則，
  - dp[i, 0] := 1
對於範圍從1到矩陣列數的j，執行：
- 如果matrix[0, j]等於1，則
  - 退出迴圈
- 否則，
  - dp[0, j] := 1
對於範圍從1到矩陣行數的i，執行：
- 對於範圍從1到矩陣列數的j，執行：
  - 如果matrix[i, j]等於1，則
    - dp[i, j] := 0
  - 否則，
    - dp[i, j] := dp[i - 1, j] + dp[i, j - 1]
返回dp的右下角的值

示例（Python）

讓我們看看下面的實現，以便更好地理解：

線上演示

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

輸入

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]

輸出

Arnab Chakraborty

更新於：2020年12月12日

340 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始