Chương trình tìm số lượng ma trận con vuông toàn số 1 bằng Python

Cho ma trận nhị phân 2D. Đếm tổng số ma trận con vuông chỉ chứa 1.

Ví dụ: ma trận 5x4 → 17 (12 ô 1x1, 4 ô 2x2, 1 ô 3x3).

Giải thuật

• Quy hoạch động tại chỗ: matrix[i][j] lưu kích thước hình vuông lớn nhất kết thúc tại (i,j).
• Nếu i==0 or j==0: res += matrix[i][j].
• Nếu matrix[i][j]==1: matrix[i][j] = min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]) + 1, res += matrix[i][j].
• Trả về res.

Ví dụ minh họa

class Solution:
    def solve(self, matrix):
        res = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i == 0 or j == 0:
                    res += matrix[i][j]
                elif matrix[i][j] == 1:
                    matrix[i][j] = min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]) + 1
                    res += matrix[i][j]
        return res

ob = Solution()
matrix = [
    [1,1,1,0],
    [1,1,1,0],
    [1,1,1,0],
    [0,0,0,0],
    [1,0,1,1]
]
print(ob.solve(matrix))

Đầu vào

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

Đầu ra

17