数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：包含全为1的最大尺寸矩形二进制子矩阵
在这个问题中，我们得到一个大小为n*m的二维矩阵bin[][]，其中包含在线二进制数，即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的元素，即如果所有元素的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
更新于：2020年12月9日
299 次浏览
广告