ขนาดสี่เหลี่ยมผืนผ้าบิナリซับเมทริกซ์สูงสุดที่มีแต่ 1 ในโปรแกรม C++

ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติ bin[][] ขนาด n*m ที่มีตัวเลขไบนารีอย่างเดียวคือ 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<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