Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दिए गए आकार के बाइनरी उप-मैट्रिक्स की संख्या पर क्वेरीज़


इस समस्या में, हमें आकार nXm का एक बाइनरी मैट्रिक्स bin[][] दिया गया है। हमारा कार्य सभी q क्वेरीज़ को हल करना है। क्वेरी(x, y) के लिए, हमें आकार x*x के उप-मैट्रिक्स की संख्या ढूंढनी होगी जैसे कि सरणी y के सभी तत्व (बाइनरी संख्या)।

समस्या विवरण

यहां, हमें दिए गए आकार के उप-मैट्रिक्स की कुल संख्या गिननी होगी जिसमें केवल दो बिट्स में से एक होता है यानी उप-मैट्रिक्स जिसके सभी तत्व 0/1 हैं।

आइए एक उदाहरण लेकर समस्या को समझते हैं,

इनपुट

n = 3, m = 4
bin[][] = {{ 1, 1, 0, 1},
           { 1, 1, 1, 0},
           { 0, 1, 1, 1}}
q = 1
q1 = (2, 1)

आउटपुट

2

व्याख्या

आकार 2 के सभी उप-मैट्रिक्स जिनके सभी तत्व 1 हैं -

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

इस समस्या का समाधान डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करना है। हल करने के लिए, हम एक 2D मैट्रिक्स DP[][] बनाए रखेंगे जो समान बिट के सबसे बड़े उप-मैट्रिक्स को संग्रहीत करेगा। यानी DP[i][j] उस उप-मैट्रिक्स का मान संग्रहीत करेगा जिसका अंतिम सूचकांक (i, j) है, और सभी तत्व समान हैं।

आपकी समझ के लिए, यदि DP[4][5] = 2, तो bin[3][4], bin[3][5], bin[4][4] और bin[4][5] पर तत्व समान हैं।

तो, DP[i][j] ढूंढने के लिए, हमारे पास दो मामले हैं -

मामला 1 - यदि i = 0 या j = 0: DP[i][j] = 1, क्योंकि केवल एक उप-मैट्रिक्स संभव है।

मामला 2 - अन्यथा, bin[i-(k-1)][j] = bin[i][j-(k-1)] ...: इस मामले में DP[i][j] = min(DP[i][j-1], DP[i-1][j], DP[i-1][j-1]) + 1। यह उस उप-मैट्रिक्स में योगदान देगा जिसकी हमें आवश्यकता है। आइए k = 2 के साथ सामान्यीकृत करें, यानी यदि हम 2x2 आकार के उप-मैट्रिक्स पर विचार करते हैं। तो हमें जांचना होगा कि क्या bin[i][j] = bin[i][j-1] = bin[i-1][j] = bin[i-1][j-1], यदि यह संभव है तो हम k=2 के लिए DP[i][j] ढूंढेंगे।

यदि मामला 2 की शर्तें पूरी नहीं होती हैं, तो हम DP[i][j] = 1 सेट करेंगे, जिसे डिफ़ॉल्ट मान माना जा सकता है।

DP[i][j] का यह मान सेट बिट या अनसेट बिट के लिए हो सकता है। हम यह देखने के लिए bin[i][j] के मान की जांच करेंगे कि k मान सेट या अनसेट मानों में से किससे संबंधित है। आवृत्तियों को ढूंढने के लिए, हम दो सरणियाँ बनाएंगे, zeroFrequency उप-मैट्रिक्स की आवृत्ति संग्रहीत करने के लिए जो 0 के लिए उत्पन्न होती है। और oneFrequency उप-मैट्रिक्स की आवृत्ति संग्रहीत करने के लिए जो 1 के लिए उत्पन्न होती है।

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,

उदाहरण

#include <iostream>
using namespace std;

#define N 3
#define M 4

int min(int a, int b, int c) {
    if (a <= b && a <= c)
        return a;
    else if (b <= a && b <= c)
        return b;
    else
        return c;
}

int solveQuery(int n, int m, int bin[N][M], int x, int y) {
    int DP[n][m], max = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0)
                DP[i][j] = 1;
            else if ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {
                DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;
                if (max < DP[i][j])
                    max = DP[i][j];
            } else
                DP[i][j] = 1;
        }
    }
    int zeroFrequency[n + m] = { 0 }, oneFrequency[n + m] = { 0 };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (bin[i][j] == 0)
                zeroFrequency[DP[i][j]]++;
            else
                oneFrequency[DP[i][j]]++;
        }
    }
    for (int i = max - 1; i >= 0; i--) {
        zeroFrequency[i] += zeroFrequency[i + 1];
        oneFrequency[i] += oneFrequency[i + 1];
    }
    if (y == 0)
        return zeroFrequency[x];
    else
        return oneFrequency[x];
}

int main() {
    int n = 3, m = 4;
    int mat[N][M] = {
        { 1, 1, 0, 1 },
        { 1, 1, 1, 0 },
        { 0, 1, 1, 1 }
    };
    int Q = 2;
    int query[Q][2] = { { 2, 1 }, { 1, 0 } };
    for (int i = 0; i < Q; i++) {
        cout << "क्वेरी " << (i + 1) << " के लिए: दिए गए आकार के बाइनरी उप-मैट्रिक्स की संख्या है "
             << solveQuery(n, m, mat, query[i][0], query[i][1]) << "\n";
    }
    return 0;
}

आउटपुट

क्वेरी 1 के लिए: दिए गए आकार के बाइनरी उप-मैट्रिक्स की संख्या है 2
क्वेरी 2 के लिए: दिए गए आकार के बाइनरी उप-मैट्रिक्स की संख्या है 3

  1. C++ में दिए गए आकार के आयत के अंदर संभावित समचतुर्भुजों की संख्या गिनना C++ में दिए गए आकार के आयत के अंदर संभावित समचतुर्भुजों की संख्या गिनना

    हमें ऊंचाई × चौड़ाई आयामों वाला एक आयत दिया गया है। आयत को 2D निर्देशांक प्रणाली पर दर्शाया गया है जिसका निचला-बायाँ कोना बिंदु (0,0) पर है। लक्ष्य इस आयत के अंदर संभावित समचतुर्भुजों की संख्या गिनना है जो निम्न शर्तों को पूरा करते हैं: समचतुर्भुज का क्षेत्रफल 0 से अधिक हो। समचतुर्भुज के व

  1. C++ में जांचें कि दिया गया बाइनरी ट्री सम-ट्री है या नहीं C++ में जांचें कि दिया गया बाइनरी ट्री सम-ट्री है या नहीं

    यहां हम देखेंगे कि बाइनरी ट्री सम-ट्री (SumTree) है या नहीं, इसकी जांच कैसे करें। अब सवाल यह है कि सम-ट्री क्या है। एक सम-ट्री एक बाइनरी ट्री है जहां एक नोड अपने बच्चों के योग का मान रखता है। ट्री का रूट उसके नीचे के सभी तत्वों का पूरा योग रखता है। यह सम-ट्री का एक उदाहरण है -इसे जांचने के लिए, हम ए

  1. - C++ प्रोग्राम: ऑक्टल संख्या को बाइनरी संख्या में बदलना

    परिचय कंप्यूटर सिस्टम में, बाइनरी संख्या बाइनरी अंक प्रणाली (आधार 2) में व्यक्त की जाती है जबकि ऑक्टल संख्या ऑक्टल अंक प्रणाली (आधार 8) में होती है। बाइनरी और ऑक्टल संख्याओं के उदाहरण बाइनरी संख्याऑक्टल संख्या 0110115 001015 1011026 0101012 C++ प्रोग्राम उदाहरण #include <iostream> #in