সি++-এ বাইনারি ম্যাট্রিক্সে ১-ধন সাবম্যাট্রিক্স সংখ্যা গণনার প্রোগ্রাম

সমস্যা বিবরণ

একটি ২D বাইনারি ম্যাট্রিক্স দেওয়া আছে। শুধু 1 দিয়ে গঠিত সকল সাবম্যাট্রিক্সের মোট সংখ্যা বের করতে হবে।

উদাহরণ ম্যাট্রিক্স:

সমাধানের পদ্ধতি

1. প্রতিটি সারি প্রক্রিয়া করুন, হিস্টোগ্রাম স্টাইলেই উচ্চতা বিল্ড আপ করুন।
2. temp[j] = সারি i-তে কলাম j-এ folyamater ১-এর সংখ্যা।
3. প্রতিটি সারির জন্য getAns(temp) ফাংশন কল করুন যেটি মনোটোনিক স্ট্যাক ব্যবহার করে সাবঅ্যারে গণনা করে।
4. স্ট্যাকে ইনডেক্স রাখা হয় যাতে বাম পাশের প্রথম ছোট মান পাওয়া যায়।
5. প্রতিটি পজিশনের জন্য সাবম্যাট্রিক্স কাউন্ট যোগ করুন।

উদাহরণ কোড

#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 i : v) ret += i;
        return ret;
    }

    int solve(vector<vector<int>>& v) {
        int ret = 0, 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 main() {
    vector<vector<int>> matrix = {{1,1,0},{1,1,0},{0,0,1}};
    cout << solve(matrix);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {{1,1,0},{1,1,0},{0,0,1}}

আউটপুট: 10