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
     
      #include
      
       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]
       
        Max) Max=f[i][j]*(r-l+1);            }        printf("%d\n",Max);    }    return 0;}