Problem(A22):Party
Judge Info
Memory Limit: 32768KB
Case Time Limit: 10000MS
Time Limit: 10000MS
Judger: Number Only Judger
Description
Frog Frank is going to have a party, he needs a large empty rectangular place. He ranted a large rectangular place in the forest, unfortunately the place is not empty, there are some trees in it. For solving the problem, he makes a map of the rectangular place with m × n grid, he paint the grid to black if there are some trees in it. Now, all he needs to do is find the largest rectangular place in the map contains no black grid.
Task
Frank is asking your help to find out, the area(the number of grids) of the largest rectangular place without black grid.
Input
The first line of input contains , the number of test cases. For each test case, the first contains two integer number m and n , denotes the size of the map. In the next m lines, each line contains a string with n ’0’,’1’ characters, ’0’ denotes the empty grid, ’1’ denotes the black grid.
Output
For each test case, print the area(the number of grids) of the largest rectangular place in a line.
Sample Input
2
3 3
111
100
111
5 5
10101
00100
00000
00000
00001
Sample Output
2
12
分析:n,m最大值为10,总时间竟然给了10s!本来还担心时间问题,一看这规模完全不用了.
注:我把本题中01地位互换了一下.
设f[i][j]为第i行第j列左边有多少个连续的1(包括第j列)
对于某个f[i][j]如果f[i-1][j]>f[i][j],那不妨扩充一层,向下类似,直到f[x][j]>f[i][j]为止.这样我们就得到了一个由[i,j]张成的矩形.通过比较这n*m个矩形就可以得出最大面积了.
#include<stdio.h>
#include<string.h>
char s[15][15];
int f[15][15];
int main()
{
int T;
scanf("%d",&T);
int n,m;
while (T--)
{
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
int i,j,k;
for (i=1;i<=n;i++) scanf("%s",s[i]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (s[i][j-1]=='0') f[i][j]=1;
else f[i][j]=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (f[i][j]==1) f[i][j]=f[i][j-1]+1;
int Max=0,l,r;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
for (k=i;k>=1;k--)
if (f[k-1][j]<f[i][j])
{
l=k;
break;
}
for (k=i;k<=n;k++)
if (f[k+1][j]<f[i][j])
{
r=k;
break;
}
if (f[i][j]*(r-l+1)>Max) Max=f[i][j]*(r-l+1);
}
printf("%d
",Max);
}
return 0;
}