इस समस्या में, हमें nXm आकार का एक बाइनरी मैट्रिक्स बिन [] [] दिया जाता है। हमारा कार्य सभी 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
स्पष्टीकरण
सभी तत्व 1 के साथ आकार 2 के सभी उप-मैट्रिक्स हैं -
{{ 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) है, और सभी तत्व समान हैं।
आपकी समझ के लिए, यदि डीपी [4] [5] =2, बिन [3] [4], बिन [3] [5], बिन [4] [4] और बिन [4] [5] में तत्व समान हैं। ।
तो, DP[i][j] खोजने के लिए, हमारे पास दो मामले हैं -
केस 1 - यदि i =0 orj =0 :DP[i][j] =1, क्योंकि केवल एक उप-मैट्रिक्स संभव हो सकता है।
केस 2 - अन्यथा, बिन[i-(k-1)][j] =bin[i][j - (k-1)]…:इस मामले में DP[i][j] =min(DP[i][i][i] j-1] , DP[i -1][j], DP[i-1][j-1] ) + 1. यह सब-मैट्रिक्स में योगदान देगा, जैसे हमें चाहिए। आइए k =2 के मामले को सामान्य करें, यानी यदि हम आकार 2X2 के उप-मैट्रिक्स पर विचार करें। फिर हमें यह जांचने की आवश्यकता है कि क्या बिन [i] [j] =बिन [i] [j - 1] =बिन [i- 1] [j] =बिन [i -1] [j -1], यदि यह संभव है फिर, हम k =2 के लिए DP[i][j] पाएंगे।
यदि केस 2 की शर्तें पूरी नहीं होती हैं, तो हम DP[i][j] =1 सेट करेंगे, जिसे डिफ़ॉल्ट मान के रूप में माना जा सकता है।
DP[i][j] का यह मान एक सेट बिट या अनसेट बिट के लिए हो सकता है। हम यह देखने के लिए बिन [i] [j] के मूल्य की जांच करेंगे कि k मान किस सेट या अनसेट मानों से संबंधित है। फ़्रीक्वेंसी खोजने के लिए, हम दो सरणियाँ बनाएंगे, ज़ीरोफ़्रीक्वेंसी, सब-मैट्रिक्स की फ़्रीक्वेंसी को स्टोर करने के लिए जो 0 के लिए जेनरेट होती है। और एक फ़्रीक्वेंसी सब-मैट्रिक्स की फ़्रीक्वेंसी को स्टोर करने के लिए जो 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<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is " <<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";
}
return 0;
} आउटपुट
For Query 1: The number of Binary sub-matrices of Given size is 2 For Query 2: The number of Binary sub-matrices of Given size is 3