ในปัญหานี้ เราได้รับ 2-D matrix 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 เท่านั้น และสำหรับสิ่งนี้ เราต้องหาพื้นที่สูงสุดจนกว่าแถวปัจจุบันจะสร้างด้วยสี่เหลี่ยมผืนผ้า
พื้นที่จนถึงแถวปัจจุบันจะคำนวณโดยหาจำนวนที่ต่อเนื่องกันจนถึงองค์ประกอบปัจจุบันในคอลัมน์ก่อน และเราจะพิจารณาองค์ประกอบที่มีจำนวนเท่ากันหรือมากกว่าหนึ่งครั้ง เช่น หากทั้งหมดมีจำนวนต่างกัน เราจะพิจารณาจำนวนที่น้อยที่สุด แถวที่มีพื้นที่มากที่สุดจะเป็นผลลัพธ์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
