Largest Submatrix of All 1’s

Description

Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.

给定一个 m-by-n (0,1)-矩阵，它的所有子矩阵中，哪个是最大的？ 最大的意思是子矩阵的元素最多。

Input

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 2000) on line. Then come the elements of a (0,1)-matrix in row-major order on m lines each with n numbers. The input ends once EOF is met.

输入包含多个测试用例。 每个测试用例以线上的 m 和 n (1≤ m，n ≤2000)开始。 然后得到 m 行上具有 n 个数的(0,1)-矩阵的行主序元素。 输入结束，一旦 eof 被满足。

Output

For each test case, output one line containing the number of elements of the largest submatrix of all 1’s. If the given matrix is of all 0’s, output 0.

对于每个测试用例，输出一行，其中包含所有1的最大子矩阵的元素个数。 如果给定的矩阵都是0，则输出0。

Sample Input

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

Sample Output

0
4

题意分析

求仅由0，1组成的矩阵中，全部由1组成的小矩阵的最大面积。

解题思路

这个是【HDU.2559】Largest Rectangle in a Histogram（单调栈）的升级版，把一维的操作变成二维的即可。这之前需要一个预处理（找矩阵的高）

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,o,s,tail,l[2005],r[2005],f[2005],a[2005][2005];
int main()
{
   
	while(cin>>n>>m)
	{
   
		for(int i=1;i<=n;i++)//输入
		 for(int j=1;j<=m;j++)
		  scanf("%lld",&a[i][j]);//要用scanf和printf，否则超时
		for(int j=1;j<=m;j++)  //矩阵的高
		{
   
			o=0;
			for(int i=1;i<=n;i++)
			 if(a[i][j]==1){
   o++;a[i][j]=o;}
			 else o=0; 
		}
		s=0;
		for(int i=1;i<=n;i++) //矩阵的宽
		{
   
			tail=0;//清零
			for(int j=1;j<=m;j++)//单调栈（找最左端）
			{
   
				while(a[i][j]<=a[i][f[tail]]&&tail>=1)tail--;
				if(tail!=0)l[j]=f[tail];
				else l[j]=0;
				f[++tail]=j;
			}
			tail=0;//清零
			for(int j=m;j>=1;j--)//单调栈（在最右端）
			{
   
				while(a[i][j]<=a[i][f[tail]]&&tail>=1)tail--;
				if(tail!=0)r[j]=f[tail];
				else r[j]=m+1;
				f[++tail]=j;
			}
			for(int j=1;j<=m;j++)//找最大值
			 s=max(a[i][j]*(r[j]-l[j]-1),s);
		}
		printf("%lld\n",s);
	}
}

谢谢