最大0 1矩阵

题目来源：http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1017

 

最大0，1子矩阵

Time Limit(Common/Java):6000MS/20000MS          Memory Limit:65536KByte
Total Submit:600            Accepted:123

Description

在一个0,1 方阵中找出其中最大的全0 子矩阵，所谓最大是指O 的个数最多

Input

单组数据第一行为整数N ，其中1<=N<=2000 ，为方阵的大小，紧接着N 行每行均有N 个0 或1 ，相邻两数间严格用一个空格隔开

Output

输出仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数

Sample Input

5
0 1 0 1 0
0 0 0 0 0
0 0 0 0 1
1 0 0 0 0

Sample Output

9

Source

Narashy

 

解题思路：

用h[j]记录第j列到当前行的连续0的个数
用l[j]记录当前行 <=j列的不小于h[j]的位置。初始值：l[j]=j;
用r[j]记录当前行 >=j 列的不小于h[j]的列位置。初始值：r[j]=j;
则在每一行的每一个不小于h[j]的最大面积为h[j]*(r[j]-l[j]+1);
全局最大面积则产生所有的h[j]里。复杂度O(n^2)

 

代码：

#include <iostream>
#include <stdio.h>
#define N 2001
int  a[N][N];
int h[N];
int l[N];
int r[N];
int main()
{
    int n;
    int i, j ,k;

    while(scanf("%d",&n)!= EOF)
    {
        for ( i = 1; i<= n; ++i )
           for ( j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);
        for ( i = 1; i <= n; ++i )
            h[i] = 0;
        int ans = 0;
        for ( i = 1; i <= n; ++i )
        {
            for ( j = 1; j <= n; ++j )
            {
                if ( a[i][j] )
                    h[j] = 0;
                else
                    ++h[j];
            }

            for ( j = 1; j <= n; ++j )
            {
                l[j] = j;
                while ( l[j] -1 >= 1 && h[l[j] - 1] >= h[j] )
                    l[j] = l[l[j] - 1];
            } 

            for ( j = n; j >= 1; --j )
            {
                r[j] = j;
                while ( r[j] + 1 <= n && h[r[j]+1] >= h[j] )
                   r[j] = r[r[j]+1];
            }

            for ( j = 1; j <= n; ++j )
            {
                int t = (r[j]-l[j]+1)*h[j];
                if ( t > ans )
                    ans = t;
            }
        }
        printf("%d\n", ans);

    }
    return 0;
}