এই সমস্যায়, আমাদেরকে n*m আকারের একটি 2-D ম্যাট্রিক্স বিন [][][] দেওয়া হয়েছে যাতে লাইন বাইনারি সংখ্যা যেমন 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
