इस समस्या में, हमें n*m आकार का 2-डी मैट्रिक्स बिन [] [] दिया जाता है जिसमें ऑनलाइन बाइनरी नंबर होते हैं यानी 0/1। हमारा काम सभी 1s के साथ अधिकतम आकार के आयत बाइनरी सब-मैट्रिक्स को खोजने और अधिकतम क्षेत्र को वापस करने के लिए एक प्रोग्राम बनाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
bin[][] = {
{1, 0, 1, 1, 1}
{0, 1, 1, 1, 1}
{0, 0, 1, 1, 1}
{1, 1, 1, 1, 1}
} आउटपुट
12
स्पष्टीकरण
इस आयत के लिए अधिकतम क्षेत्रफल वाला क्षेत्रफल।
1, 1, 1 1, 1, 1 1, 1, 1 1, 1, 1
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें केवल 1 से मिलकर सबसे बड़ा संभव आयताकार सबमैट्रिक्स खोजने की आवश्यकता है। और इसके लिए हमें अधिकतम क्षेत्रफल ज्ञात करना होगा जब तक कि वर्तमान पंक्ति एक आयत द्वारा नहीं बनाई जाती है।
वर्तमान पंक्ति तक के क्षेत्र की गणना पहले कॉलम में वर्तमान तत्व तक लगातार लोगों की संख्या का पता लगाकर की जाएगी। और हम समान या अधिक संख्या वाले तत्वों पर एक बार विचार करेंगे अर्थात यदि सभी की अलग-अलग संख्याएँ हैं, तो हम सबसे छोटी संख्या पर विचार करेंगे। अब तक के सबसे बड़े क्षेत्रफल वाली पंक्ति का परिणाम होगा
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
int calcAreaTillRow(int row[]){
stack<int> area1s;
int tos;
int maxArea = 0;
int curArea = 0;
int i = 0;
while (i < C) {
if (area1s.empty() || row[area1s.top()] <= row[i])
area1s.push(i++);
else {
tos = row[area1s.top()];
area1s.pop();
curArea = tos * i;
if (!area1s.empty())
curArea = tos * (i − area1s.top() − 1);
maxArea = max(curArea, maxArea);
}
}
while (!area1s.empty()) {
tos = row[area1s.top()];
area1s.pop();
curArea = tos * i;
if (!area1s.empty())
curArea = tos * (i − area1s.top() − 1);
maxArea = max(curArea, maxArea);
}
return maxArea;
}
int calcmaxRecSubMat1(int bin[][C]){
int result = calcAreaTillRow(bin[0]);
for (int i = 1; i < R; i++) {
for (int j = 0; j < C; j++)
if (bin[i][j])
bin[i][j] += bin[i − 1][j];
result = max(result, calcAreaTillRow(bin[i]));
}
return result;
}
int main(){
int bin[][C] = {
{1, 0, 1, 1, 1},
{0, 1, 1, 1, 1},
{0, 0, 1, 1, 1},
{1, 1, 1, 1, 1}
};
cout<<"The area of maximum size rectangle binary sub−matrix with all 1s is "<<calcmaxRecSubMat1(bin);
return 0;
} आउटपुट
The area of maximum size rectangle binary sub-matrix with all 1s is 12