C++ में दिए गए मैट्रिक्स में 1s के वर्ग सबमैट्रिक्स की संख्या गिनने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है, हमें सभी 1s वाले सबमैट्रिक्स की कुल संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट 10 होगा, क्योंकि पांच 1×1 मैट्रिक्स, दो 2×1 मैट्रिक्स, दो 1×2 मैट्रिक्स और एक 2×2 मैट्रिक्स हैं।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. एक फंक्शन getAns() परिभाषित करें जो एक ऐरे a लेता है
2. ret := 0
3. n := a का आकार
4. आकार n का एक ऐरे v परिभाषित करें
5. एक स्टैक st परिभाषित करें
6. i := 0 से a के आकार तक:
   • जब तक (st खाली नहीं है और a[st का शीर्ष] ≥ a[i]): st से पॉप करें
   • यदि st खाली नहीं है:
     • prev := st का शीर्ष
     • v[i] := v[i] + v[prev]
     • v[i] := v[i] + a[i] * (i - prev)
   • अन्यथा: v[i] := v[i] + a[i] * (i + 1)
   • i को st में डालें
7. v के प्रत्येक i के लिए: ret := ret + i
8. ret वापस करें
9. मुख्य विधि से:
   • ret := 0
   • n := v का आकार
   • m := (यदि n शून्येतर है तो v[0] का आकार अन्यथा 0)
   • आकार m का एक ऐरे temp परिभाषित करें
   • i := 0 से n-1 तक:
     • j := 0 से m-1 तक: temp[j] := (यदि v[i][j] शून्येतर है तो temp[j] + 1 अन्यथा 0)
     • ret := ret + getAns(temp)
   • ret वापस करें

उदाहरण

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

class Solution {
public:
    int getAns(vector<int>& a) {
        int ret = 0;
        int n = a.size();
        vector<int> v(n);
        stack<int> st;
        for (int i = 0; i < a.size(); 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 i : v) {
            ret += i;
        }
        return ret;
    }
    
    int solve(vector<vector<int>>& v) {
        int ret = 0;
        int n = v.size();
        int 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);
}

इनपुट

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

आउटपुट

10