โปรแกรมนับจำนวนเมทริกซ์ย่อยสี่เหลี่ยมที่มีแต่ 1 ใน C++

ให้เมทริกซ์ไบนารี 2 มิติ ต้องการนับจำนวนเมทริกซ์ย่อย (ทุกรูปทรงสี่เหลี่ยม) ที่ประกอบด้วย 1 ทุกเซลล์

ตัวอย่าง: 1 1 0 1 1 0 0 0 1 ผลลัพธ์ = 10 (1×1: 5, 2×1: 2, 1×2: 2, 2×2: 1)

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชัน getAns(a) ใช้อัลกอริทึม Monotonic Stack นับสี่เหลี่ยมในฮิสโตแกรม
2. หลักการ: แปลงแต่ละแถวเป็นฮิสโตแกรมความสูงของ 1 ติดต่อกัน
3. สำหรับแต่ละแถว:
   • อัปเดตความสูง: temp[j] = (v[i][j] ? temp[j]+1 : 0)
   • เรียก getAns(temp) บวกเข้าผลรวม

ตัวอย่างโค้ด 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] + 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 main() {
    vector<vector<int>> matrix = {{1,1,0},{1,1,0},{0,0,1}};
    cout << (new Solution())->solve(matrix);
    return 0;
}

อินพุต

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

เอาต์พุต

10