এই সমস্যায়, আমাদেরকে বাইনারি সংখ্যা (0/1) সমন্বিত nXn আকারের একটি 2-ডি ম্যাট্রিক্স দেওয়া হয়েছে। আমাদের কাজ হল সর্বাধিক সাবম্যাট্রিক্সারিয়া খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা যেখানে 0 এর গণনার চেয়ে 1 এর একটি বেশি রয়েছে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
bin[N][N] = {
{0, 1, 0, 0},
{1, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1}
} আউটপুট
9
ব্যাখ্যা
submatrix : bin[1][0], bin[1][1], bin[1][2] bin[2][0], bin[2][1], bin[2][2] bin[3][0], bin[3][1], bin[3][2] is the largest subarray with more 1’s one more than 0’s. Number of 0’s = 4 Number of 1’s = 5
সমাধান পদ্ধতি
একটি সহজ পদ্ধতি হল ম্যাট্রিক্স থেকে সম্ভাব্য সমস্ত সাবম্যাট্রিক্স খুঁজে বের করা এবং তারপর সবগুলোর মধ্যে সর্বাধিক ক্ষেত্রফল ফেরত দেওয়া।
এই পদ্ধতিটি চিন্তা করা এবং প্রয়োগ করা সহজ কিন্তু অনেক সময় নেয় এবং লুপগুলির নেস্টিং প্রয়োজন যা অর্ডারের সময় জটিলতা তৈরি করে O(n^4) তাই, আসুন আরও একটি পদ্ধতি নিয়ে আলোচনা করা যাক যা আরও কার্যকর।
এখানে ধারণাটি হল ম্যাট্রিক্সের বাম এবং ডানদিকে কলামগুলি ঠিক করা এবং তারপরে সবচেয়ে বড় সাব্যারে খুঁজে বের করা যার সংখ্যা 1 এর সংখ্যার চেয়ে 0 এর এক বেশি। আমরা প্রতিটি সারিতে যোগফল গণনা করব এবং তারপরে এটিকে জমা করব। 0 এর সংখ্যার চেয়ে 1 এর এক বেশি গণনা সহ সর্বাধিক এলাকা খুঁজে বের করতে।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){
unordered_map<int, int> subArr;
int sumVal = 0, maxSubArrLen = 0;
for (int i = 0; i < n; i++) {
sumVal += row[i];
if (sumVal == 1) {
startInd = 0;
finishInd = i;
maxSubArrLen = i + 1;
}
else if (subArr.find(sumVal) == subArr.end())
subArr[sumVal] = i;
if (subArr.find(sumVal − 1) != subArr.end()) {
int currLen = (i − subArr[sumVal − 1]);
if (maxSubArrLen < currLen)
startInd = subArr[sumVal − 1] + 1;
finishInd = i;
maxSubArrLen = currLen;
}
}
return maxSubArrLen;
}
int largestSubmatrix(int bin[SIZE][SIZE], int n){
int rows[n], maxSubMatArea = 0, currArea, longLen, startInd,
finishInd;
for (int left = 0; left < n; left++) {
memset(rows, 0, sizeof(rows));
for (int right = left; right < n; right++) {
for (int i = 0; i < n; ++i){
if(bin[i][right] == 0)
rows[i] −= 1;
else
rows[i] += 1;
}
longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
currArea = (finishInd − startInd + 1) * (right − left + 1);
if ((longLen != 0) && (maxSubMatArea < currArea)) {
maxSubMatArea = currArea;
}
}
}
return maxSubMatArea;
}
int main(){
int bin[SIZE][SIZE] = {
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 1 }
};
int n = 4;
cout<<"The maximum sub−matrix area having count of 1’s one more
than count of 0’s is "<<largestSubmatrix(bin, n);
return 0;
} আউটপুট
The maximum sub-matrix area having count of 1’s one more than count of 0’s is 9
