首页 > 代码库 > zoj 2180 - City Game

zoj 2180 - City Game

题目:给你一个1000*1000的01矩阵,求里面全是1的最大矩形面积。

分析:dp,单调队列。zju1985升级版 ^_^ 继上次那道题想了一天。

            本来想用O(N^2)的最大正方形求解,想错了今天仔细一看,其实这道题目就是二维的最大矩形;

            我们将问题分解成最大矩形,即求解以k行为底边的图形中的最大矩形,然后合并,求最大的矩形;
          
            预处理: 求出以每行为底边的每一列从底边开始向上的最大连续1的高度MaxH。 O(N^2) ;

            DP:对于每一层底边,我们利用单调队列求解出本行的最大矩形。 O(N);

            关于单调队列的求解分析,可参照zoj1985的题解;

            总体时间:T(N) = O(N^2)+O(N)*O(N) = O(N^2)。

说明: (2011-09-19 01:36)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char Maps[ 1003 ][ 1003 ];
int  MaxH[ 1003 ][ 1003 ];
int  L[ 1003 ],R[ 1003 ];
int  MUQ[ 1003 ];

int main()
{
    int t,m,n;
    while ( scanf("%d",&t) != EOF )
    while ( t -- ) {
        scanf("%d%d",&m,&n);getchar();
        for ( int i = 1 ; i <= m ; ++ i )
        for ( int j = 1 ; j <= n ; ++ j ) {
            scanf("%c",&Maps[ i ][ j ]);
            getchar();
        }
        
        //计算每条底边上的每列高度 
        memset( MaxH, 0, sizeof( MaxH ) );
        for ( int i = 1 ; i <= m ; ++ i )
        for ( int j = 1 ; j <= n ; ++ j )
            if ( Maps[ i ][ j ] == 'F' )
                MaxH[ i ][ j ] = MaxH[ i-1 ][ j ]+1;
            else 
                MaxH[ i ][ j ] = 0;
            
        for ( int i = 1 ; i <= m ; ++ i )
            MaxH[ i ][ 0 ] = MaxH[ i ][ n+1 ] = -1;

        int MaxV = 0;
        for ( int i = 1 ; i <= m ; ++ i ) {
            //计算每个点的左边界 
            int tail = 0;
            MUQ[ 0 ] = 0;
            for ( int j = 1 ; j <= n+1 ; ++ j ) {
                while ( tail >= 0 && MaxH[ i ][ MUQ[ tail ] ] > MaxH[ i ][ j ] )
                        R[ MUQ[ tail -- ] ] = j;
                MUQ[ ++ tail ] = j;    
            }
            //计算每个点的右边界 
                tail = 0;
            MUQ[ 0 ] = n+1;
            for ( int j = n ; j >= 0 ; -- j ) {
                while ( tail >= 0 && MaxH[ i ][ MUQ[ tail ] ] > MaxH[ i ][ j ] )
                    L[ MUQ[ tail -- ] ] = j;
                MUQ[ ++ tail ] = j;    
            }
            //求解
            for ( int j = 1 ; j <= n ; ++ j ) {
                int Temp = MaxH[ i ][ j ]*(R[ j ]-L[ j ]-1);
                if ( MaxV < Temp )
                    MaxV = Temp; 
            }
        }
        
        printf("%d\n",MaxV*3);
    }
    return 0;
}

zoj 2180 - City Game