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

Cho ma trận nhị phân m x n. Đếm số ma trận con vuông (cạnh bằng nhau) chứa toàn số 1.

Ví dụ:
0 1 1 1
1 1 1 1
0 1 1 1
Kết quả là 15: 10 vuông 1x1, 4 vuông 2x2, 1 vuông 3x3.

Thuật toán giải quyết (Quy hoạch động)

• Nếu ma trận chỉ có một phần tử 1, trả về 1.
• rows, cols := kích thước ma trận.
• result := 0.
• Duyệt từng ô (row, col):
  • Nếu row == 0 hoặc col == 0: nếu matrix[row][col] == 1, result += 1.
  • Ngược lại, nếu matrix[row][col] == 1:
    • square := 1 + min(matrix[row-1][col], matrix[row][col-1], matrix[row-1][col-1]).
    • Cập nhật matrix[row][col] = square (lưu độ cạnh vuông lớn nhất kết thúc tại ô này).
    • result += square.
• Trả về result.

Ý tưởng: dp[i][j] lưu cạnh vuông toàn 1 lớn nhất có góc dưới phải tại (i,j). Giá trị này bằng 1 + min(3 ô lân cận trên, trái, chéo).

Ví dụ triển khai

def solve(matrix):
    if matrix == [[1]]:
        return 1
    rows = len(matrix)
    cols = len(matrix[0])
    result = 0
    for row in range(rows):
        for col in range(cols):
            if (row == 0 or col == 0):
                if matrix[row][col] == 1:
                    result += 1
            elif matrix[row][col] == 1:
                square = min(matrix[row-1][col], matrix[row][col-1], matrix[row-1][col-1]) + 1
                matrix[row][col] = square
                result += square
    return result

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

Đầu vào

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

Đầu ra

15