程序查找在Python中从左上角到右下角的方法

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个N x M的二进制矩阵。其中0表示空白单元格，而1表示被阻止的单元格。现在从左上角开始，我们必须找到到达右下角的多种方法。如果答案很大，则将其修改为10 ^ 9 + 7。

所以，如果输入像

那么输出将为2，因为有两种方法可以到达右下角：[右，下，右，下]和[下，右，右，下]。

范例(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] ]

2

以上是 程序查找在Python中从左上角到右下角的方法 的全部内容， 来源链接： utcz.com/z/330758.html