数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究在 C++ 中找出最大子矩阵区域，其中 1 的计数比 0 的计数多一个
在本教程中，我们将讨论一项程序，用于查找最大子矩阵区域，其中 1 的计数比 0 的计数多一个。
为此，我们将获得一个包含 0 和 1 的矩阵。我们的任务是获取包含 1 多于 0 的最大面积的子矩阵
示例
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
//finding length of longest sub-matrix
int lenOfLongSubarr(int arr[],
int n, int& start, int& finish) {
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == 1) {
start = 0;
finish = i;
maxLen = i + 1;
}
else if (um.find(sum) == um.end()) um[sum] = i;
if (um.find(sum - 1) != um.end()) {
if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1;
finish = i;
maxLen = i - um[sum - 1];
}
}
return maxLen;
}
//finding the maximum area
void largestSubmatrix(int mat[SIZE][SIZE], int n) {
int finalLeft, finalRight, finalTop, finalBottom;
int temp[n], maxArea = 0, len, start, finish;
for (int left = 0; left < n; left++) {
memset(temp, 0, sizeof(temp));
for (int right = left; right < n; right++) {
for (int i = 0; i < n; ++i)
temp[i] += mat[i][right] == 0 ? -1 : 1;
len = lenOfLongSubarr(temp, n, start, finish);
if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) {
finalLeft = left;
finalRight = right;
finalTop = start;
finalBottom = finish;
maxArea = (finish - start + 1) * (right - left + 1);
}
}
}
cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n";
cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n";
cout << "Maximum area: " << maxArea;
}
int main() {
int mat[SIZE][SIZE] = {
{ 1, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 1 }
};
int n = 4; largestSubmatrix(mat, n);
return 0;
}输出
(Top, Left): (1, 1) (Bottom, Right): (3, 3) Maximum area: 9
更新于：2020 年 7 月 10 日
75 次浏览
广告