Chương trình tìm số cách chúng ta có thể tiếp cận từ điểm trên cùng bên trái đến điểm dưới cùng bên phải bằng Python

Giả sử chúng ta có một ma trận nhị phân N x M. Trong đó 0 có nghĩa là ô trống và 1 có nghĩa là ô bị chặn. Bây giờ bắt đầu từ góc trên cùng bên trái, chúng ta phải tìm số cách để đến được góc dưới cùng bên phải. Nếu câu trả lời là rất lớn, hãy sửa đổi nó theo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2, vì Có hai cách để đến phía dưới bên phải:[Phải, Xuống, Phải, Xuống] và [Xuống, Phải, Phải, Xuống].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• dp:=ma trận có cùng kích thước của ma trận đã cho và điền bằng 0
• dp [0, 0]:=1
• đối với tôi trong phạm vi 1 đến số hàng của ma trận, hãy thực hiện
  • nếu ma trận [i, 0] giống 1, thì
    • ra khỏi vòng lặp
  • nếu không,
    • dp [i, 0]:=1
• đối với j trong phạm vi 1 đến số cột của ma trận, thực hiện
  • nếu ma trận [0, j] giống 1, thì
    • ra khỏi vòng lặp
  • nếu không,
    • dp [0, j]:=1
• đối với tôi trong phạm vi 1 đến số hàng của ma trận, hãy thực hiện
  • đối với j trong phạm vi 1 đến số cột của ma trận, thực hiện
    • nếu ma trận [i, j] giống 1, thì
      • dp [i, j]:=0
    • nếu không,
      • dp [i, j]:=dp [i - 1, j] + dp [i, j - 1]
• trả về giá trị dưới cùng bên phải của dp

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

2