# 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 ≤ mn ≤ 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.

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

```0
4```

### 我的代码

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

``````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]);
}``````

``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;
}``````