Chương trình đếm số đường đi từ góc trên trái đến góc dưới phải trong ma trận nhị phân trong Python

Cho ma trận nhị phân N×M (0: ô trống, 1: chặn). Từ góc trên trái (0,0), đếm số cách đi đến góc dưới phải (N-1, M-1) chỉ đi xuống hoặc sang phải. Kết quả modulo 10⁹+7.

Ví dụ ma trận 3x3:

0 0 1
0 0 0
1 1 0

Giải thuật (Quy hoạch động 2D)

• Khởi tạo dp cùng kích thước, dp[0][0] = 1.
• Khởi tạo hàng đầu và cột đầu: dừng khi gặp chướng ngại vật.
• Duyệt các ô còn lại: nếu ô bị chặn dp[i][j]=0, ngược lại dp[i][j] = dp[i-1][j] + dp[i][j-1].
• Trả về dp[-1][-1].

Mã nguồn Python

class Solution:
    def solve(self, matrix):
        MOD = 10**9 + 7
        n, m = len(matrix), len(matrix[0])
        dp = [[0]*m for _ in range(n)]
        dp[0][0] = 1
        for i in range(1, n):
            if matrix[i][0] == 1:
                break
            dp[i][0] = 1
        for j in range(1, m):
            if matrix[0][j] == 1:
                break
            dp[0][j] = 1
        for i in range(1, n):
            for j in range(1, m):
                if matrix[i][j] == 1:
                    dp[i][j] = 0
                else:
                    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD
        return dp[-1][-1]

ob = Solution()
matrix = [[0,0,1],[0,0,0],[1,1,0]]
print(ob.solve(matrix))  # Output: 2

Đầu vào

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

Đầu ra

2