Trong bài toán này, chúng ta được cung cấp một bin ma trận 2-D [] [] có kích thước n * m chứa các số nhị phân trực tuyến, tức là 0/1. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm ma trận con nhị phân hình chữ nhật có kích thước tối đa với tất cả các số 1 và trả về diện tích tối đa cho chúng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
bin[][] = {
{1, 0, 1, 1, 1}
{0, 1, 1, 1, 1}
{0, 0, 1, 1, 1}
{1, 1, 1, 1, 1}
} Đầu ra
12
Giải thích
Đối với hình chữ nhật này, diện tích bằng tối đa.
1, 1, 1 1, 1, 1 1, 1, 1 1, 1, 1
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề này, chúng ta cần tìm một ma trận con hình chữ nhật lớn nhất có thể chỉ chứa 1 chữ cái. Và đối với điều này, chúng ta cần tìm diện tích tối đa cho đến khi hàng hiện tại được tạo bởi một hình chữ nhật.
Diện tích cho đến hàng hiện tại sẽ được tính bằng cách tìm số đầu tiên liên tiếp cho đến phần tử hiện tại trong cột. Và chúng tôi sẽ xem xét các phần tử có cùng số hoặc lớn hơn một lần tức là nếu tất cả có số khác nhau, chúng tôi sẽ xem xét phần tử nhỏ nhất. Hàng có diện tích lớn nhất cho đến nay sẽ là kết quả
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The area of maximum size rectangle binary sub-matrix with all 1s is 12