इस समस्या में, हमें आकार 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