Chương trình Python đếm số ma trận con vuông toàn 1 trong ma trận nhị phân

Cho ma trận nhị phân 2D. Đếm tổng số ma trận con vuông (bất kỳ kích thước) mà tất cả phần tử đều là 1.

Ví dụ

0 1 1
0 1 1

Output: 5 (1 ma trận 2×2 + 4 ma trận 1×1).

Thuật toán (Dynamic Programming)

1. dp[i][j] = cạnh lớn nhất của ma trận vuông toàn 1 có góc dưới-phải tại (i,j).
2. Nếu mat[i][j] == 1:
   • Nếu ở hàng 0 hoặc cột 0: dp[i][j] = 1.
   • Ngược lại: dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1.
3. Tổng tất cả dp[i][j] = số ma trận con vuông toàn 1.
4. Có thể sửa đổi trực tiếp trên mat để tiết kiệm không gian.

Mã nguồn Python

def solve(mat):
    if not mat:
        return 0
    c = 0
    for i in range(len(mat)):
        for j in range(len(mat[0])):
            if mat[i][j] == 1:
                if i == 0 or j == 0:
                    c += 1
                else:
                    temp = min(mat[i-1][j-1], mat[i][j-1], mat[i-1][j]) + 1
                    c += temp
                    mat[i][j] = temp
    return c

# Test
matrix = [[0, 1, 1], [0, 1, 1]]
print(solve(matrix))  # Output: 5

Độ phức tạp

• Thời gian: O(m*n)
• Không gian: O(1) (sửa đổi trực tiếp ma trận đầu vào).

Lưu ý: Input ví dụ trong bài gốc có lỗi (input [[2,6],[3,4],[4,7],[5,5]] không phải ma trận nhị phân), đã sửa trong ví dụ test.