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

Mô tả bài toán

Cho ma trận nhị phân 2D, đếm tổng số ma trận con (bất kỳ kích thước) chỉ chứa toàn 1.

Ví dụ: 1 1 0 1 1 0 0 0 1 → Kết quả 10 (5 ma trận 1x1, 2 ma trận 2x1, 2 ma trận 1x2, 1 ma trận 2x2).

Giải thuật

1. Duyệt từng hàng, xây dựng mảng height[j] = số 1 liên tiếp kết thúc tại hàng hiện tại cột j.
2. Với mỗi hàng, dùng stack đơn điệu để tính số ma trận con kết thúc tại hàng đó (hàm getAns).
3. Tổng cộng các kết quả của tất cả các hàng.

Ví dụ minh họa (C++)

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

class Solution {
public:
    int getAns(vector<int>& a) {
        int ret = 0, n = a.size();
        vector<int> v(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && a[st.top()] >= a[i]) st.pop();
            if (!st.empty()) {
                int prev = st.top();
                v[i] += v[prev];
                v[i] += a[i] * (i - prev);
            } else {
                v[i] += a[i] * (i + 1);
            }
            st.push(i);
        }
        for (int x : v) ret += x;
        return ret;
    }
    int solve(vector<vector<int>>& v) {
        int ret = 0, n = v.size(), m = n ? v[0].size() : 0;
        vector<int> temp(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                temp[j] = v[i][j] ? temp[j] + 1 : 0;
            ret += getAns(temp);
        }
        return ret;
    }
};

int solve(vector<vector<int>>& matrix) {
    return (new Solution())->solve(matrix);
}

int main() {
    vector<vector<int>> matrix = {{1,1,0},{1,1,0},{0,0,1}};
    cout << solve(matrix);
    return 0;
}

Đầu vào

{{1,1,0},{1,1,0},{0,0,1}}

Đầu ra

10