POJ3494总结

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.

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.

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.

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

我的代码

这题我就是奔着练习悬线法求最大子矩阵来的。相关知识点在这里的算法2。

不能直接套板子。

递推式为，如果这个点是0，则

height[i][j]=0;
left[i][j]=firstLeft;
right[i][j]=firstRight;

其实这种情况下我们并不关系左右达到的最长长度，因为这个点构不成子矩阵。

如果这个点是1，则

height[i][j]=height[i-1][j]+1;
left[i][j]=firstLeft;
if (matrix[i-1][j]==1)
{
left[i][j]=max(left[i][j],left[i-1][j]);
}
right[i][j]=firstRight;
if (matrix[i-1][j]==1)
{
right[i][j]=min(right[i][j],right[i-1][j]);
}

当上一个点不是1的时候，说明它是这个悬线的上端点，left和right就是本身。当上一个点也是1的时候就需要比较大小了。

最后的求和也要注意一下是左右之差再减一。

ans=max(ans,(right[i][j]-left[i][j]-1)*height[i][j]);

完整代码：

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;

short matrix[2010][2010];
short left[2010][2010];
short right[2010][2010];
short height[2010][2010];
int n,m;
int main()
{
	
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		int ans=0;
		
		memset(height,0,sizeof(height));
		memset(left,0,sizeof(left));
		memset(right,0,sizeof(right));
		
		for (int i=1;i<=m;i++)
		{
			int firstLeft=0;
			for(int j=1;j<=n;j++)
			{
				scanf("%d",&matrix[i][j]);
				if (matrix[i][j]==0)
				{
					height[i][j]=0;
					firstLeft=j;
					left[i][j]=firstLeft;
				}
				else
				{
					height[i][j]=height[i-1][j]+1;
					left[i][j]=firstLeft;
					if (matrix[i-1][j]==1)
					{
						left[i][j]=max(left[i][j],left[i-1][j]);
					}
				}
			}
			
		}
		for (int i=1;i<=m;i++)
		{
			int firstRight=n+1;
			for(int j=n;j>0;j--)
			{
				if (matrix[i][j]==0)
				{
					firstRight=j;
					right[i][j]=firstRight;
				}
				else
				{
					right[i][j]=firstRight;
					if (matrix[i-1][j]==1)
					{
						right[i][j]=min(right[i][j],right[i-1][j]);
					}
				}	
			}
		}
		
		for (int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				ans=max(ans,(right[i][j]-left[i][j]-1)*height[i][j]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

反思

折腾我半天了。