面积最大的全1矩阵

题目描述：

在一个M * N的矩阵中，所有的元素只有0和1，从这个矩阵中找出一个面积最大的全1子矩阵，所谓最大是指元素1的个数最多。

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小。
矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间严格用一个空格隔开。

输出：

对应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数。

样例输入：

样例输出：

0
4

解题思路： 从第一行开始，一行一行向下扫描，记录每一列当前的1的个数（碰到0时候清零，可以理解为高度，记录其为h[i ]），然后计算每一列的符合该列高度的矩形有多宽（对第j列而言，宽度为r[j]-l[j]+1）最后遍历完所有行得到的最大面积就是答案。
AC代码：

#include
            
             
#include
             
               using namespace std; int matrix[1005][1005]; int h[1005]; int r[1005]; int l[1005]; int main(int argc,char *argv[]) { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int i,j,k; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&matrix[i][j]); } } memset(h,0,sizeof(h)); int ans=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(matrix[i][j]==1) h[j]++; else h[j]=0; } h[0]=h[m+1]=-1; for(j=1;j<=m;j++)//l[i]表示h[i]左边最远的一个h值不小于h[i]的位置 { //即l[i]到i的所有h值均>=h[i],r[i]同理 k=j; while(h[j]<=h[k-1]) k=l[k-1]; l[j]=k; } for(j=m;j>=1;j--)//r[i]表示h[i]右边最远的一个h值不小于h[i]的位置 { k=j; while(h[j]<=h[k+1]) k=r[k+1]; r[j]=k; } for(j=1;j<=m;j++) { if(ans

点击复制链接与好友分享! 回本站首页

分享到：更多

您对本文章有什么意见或着疑问吗？请到论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： 设计模式 C++实现_1_单例设计模式(简单实现)

下一篇： C++ Primer 学习笔记_40_STL实践与分析（14）--概述、初窥算法

hdu 4382 模拟矩阵连乘高精度

HDOJ - 2371 矩阵乘法

矩阵链乘法

分割矩阵 (二分范围[L,R)）

[算法设计]矩阵乘法

MPI 实现 SUMMA 矩阵乘法

最大子矩阵和变形（poj 1964 hdu 1