इस समस्या में, हमें n*m आकार का एक 2-D मैट्रिक्स bin[][] दिया गया है जिसमें केवल बाइनरी संख्याएं हैं यानी 0/1। हमारा कार्य एक प्रोग्राम बनाना है जो सभी 1 वाले अधिकतम आकार के आयताकार बाइनरी उप-मैट्रिक्स को ढूंढे और अधिकतम क्षेत्र वापस करे।
उदाहरण
इनपुट
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 से बने सबसे बड़े संभव आयताकार उपमैट्रिक्स को ढूंढना होगा। और इसके लिए, हमें वर्तमान पंक्ति तक आयत द्वारा बनाए गए अधिकतम क्षेत्र को ढूंढना होगा।
वर्तमान पंक्ति तक का क्षेत्र पहले कॉलम में वर्तमान तत्व तक लगातार 1 की संख्या ढूंढकर गणना की जाएगी। और हम उन तत्वों पर विचार करेंगे जिनमें समान या अधिक संख्या में 1 हों यानी यदि सभी की संख्या अलग है, तो हम सबसे छोटे पर विचार करेंगे। अब तक सबसे बड़े क्षेत्र वाली पंक्ति परिणाम होगी।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
int calcAreaTillRow(int row[]){
stack 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
