Chương trình đếm số ma trận con toàn số 1 bằng Python

Cho ma trận nhị phân kích thước m x n. Đếm số ma trận con (bất kỳ kích thước nào) chứa toàn số 1.

Ví dụ với ma trận:
1 0 1
0 1 1
0 1 1
Kết quả là 13: 6 ma trận 1x1, 3 ma trận 2x1, 2 ma trận 1x2, 1 ma trận 3x1 và 1 ma trận 2x2 (đề bài gốc ghi nhầm 4x4).

Thuật toán giải quyết

• m := số hàng, n := số cột.
• Tạo ma trận dp kích thước m x n khởi tạo 0.
• Tính dp[i][j] = số lượng 1 liên tiếp theo cột j kết thúc tại hàng i:
  • Nếu i == 0 và matrix[i][j] == 1: dp[i][j] = 1.
  • Nếu matrix[i][j] == 1: dp[i][j] = dp[i-1][j] + 1.
• total := 0.
• Với mỗi hàng i, với mỗi cột j:
  • Với k từ j+1 đến n:
    • total += min(dp[i][j:k]) (độ cao nhỏ nhất trong đoạn [j, k-1] cho biết số ma trận con kết thúc tại hàng i, cột từ j đến k-1).
• Trả về total.

Ví dụ triển khai

def solve(matrix):
    m = len(matrix)
    n = len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and matrix[i][j]:
                dp[i][j] = 1
            elif matrix[i][j]:
                dp[i][j] = dp[i-1][j] + 1
    total = 0
    for i in range(m):
        for j in range(n):
            for k in range(j+1, n+1):
                total += min(dp[i][j:k])
    return total

matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

Đầu vào

[[1,0,1],[0,1,1],[0,1,1]]

Đầu ra

13