সব ১ সহ সর্বোচ্চ আকারের বাইনারি সাব-ম্যাট্রিক্স আয়তন (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n×m আকারের একটি 2-D ম্যাট্রিক্স bin[][] দেওয়া আছে যেটি শুধু বাইনারি সংখ্যা অর্থাৎ ০/১ ধারণ করে। আমাদের কাজ হল সব ১ সহ সর্বোচ্চ আকারের বাইনারি সাব-ম্যাট্রিক্স আয়তন খুঁজে বের করার প্রোগ্রাম তৈরি করা এবং সর্বোচ্চ এলিয়া ফেরত দেওয়া।

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

সমস্যা সমাধানের জন্য, আমাদের শুধু ১ সহ সম্ভাব্য সবচেয়ে বড় আয়তাকার সাবম্যাট্রিক্স খুঁজে বের করতে হবে। এর জন্য, আমাদের বর্তমান সারি পর্যন্ত আয়তাকার দ্বারা তৈরি সর্বোচ্চ এলিয়া বের করতে হবে।

বর্তমান সারি পর্যন্ত এলিয়া হিসাব করা হবে কলামে বর্তমান উপাদান পর্যন্ত ਲগাতার ১-এর সংখ্যা বের করে। এবং আমরা সেই উপাদানগুলোক বিবেচনা করব যাদের একই বা অধিক সংখ্যক ১ আছে অর্থাৎ যদি সবার ভিন্ন সংখ্যা হয়, তবে আমরা সবচেয়ে ছোটটি বিবেচনা করব। সবচেয়ে বড় এলিয়া वाले সারিই ফলাফল হবে।

#include 
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