資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告