Đếm ma trận con vuông toàn 1 (Count Square Submatrices with All Ones) trong C++

Cho ma trận nhị phân m x n. Đếm số ma trận con vuông toàn chữ số 1.

Ví dụ: ma trận 3x4 cho 15 vuông (10 vuông 1x1, 4 vuông 2x2, 1 vuông 3x3).

Thuật toán (DP Bottom-Up)

1. dp[i][j] = cạnh lớn nhất của vuông toàn 1 có góc dưới-phải tại (i,j).
2. Nếu matrix[i][j]==1: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
3. Tổng tất cả dp[i][j] là kết quả.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countSquares(vector>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;
        for (int i=n-1; i>=0; i--) {
            for (int j=m-1; j>=0; j--) {
                if (matrix[i][j] == 1) {
                    if (i+1> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}};
    Solution ob;
    cout << ob.countSquares(v); // 15
    return 0;
}

Đầu vào / Đầu ra

Input: [[0,1,1,1],[1,1,1,1],[0,1,1,1]]

Output: 15