首页 > 代码库 > zoj 2067 - White Rectangles

zoj 2067 - White Rectangles

题目:一个由‘.’和‘#’组成矩形,统计里面‘.‘组成的矩形的个数。

分析:经典dp。计算之前要做很多预处理。

            状态:f(i,j)为,以点(i,j)作为右下角顶点的矩形的个数;

            首先,统计每个‘.‘元素,所在行以他为结束标志的连续的‘.‘的长度L(i,j);

            然后,从点(i,j)向左上运动,计算对应的高度的矩形个数maxL(i,j,k);

            转移:f(i,j)= sum(maxL(i,j,k)) { 其中,0 < k ≤ j };

            (maxL(i,j,k)为从k到i的每行以j为结束标志的矩形最大公共长度)。

明:(2011-11-02 12:25)。

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

char maps[ 105 ][ 105 ];
int  line[ 105 ][ 105 ];
int  minl[ 105 ][ 105 ];
int  rect[ 105 ][ 105 ];

int main()
{
    int n;
    while ( scanf("%d",&n) != EOF ) {
        for ( int i = 1 ; i <= n ; ++ i )
            scanf("%s",&maps[ i ][ 1 ]);
        
        memset( line, 0, sizeof( line ) );
        memset( rect, 0, sizeof( rect ) );
        for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= n ; ++ j )
            if ( maps[ i ][ j ] == '.' )
                line[ i ][ j ] = line[ i ][ j-1 ]+1;
        
        for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= n ; ++ j ) {
            int minL = line[ i ][ j ];
            for ( int k = i ; k >= 1 ; -- k ) {
                if ( minL > line[ k ][ j ] )
                    minL = line[ k ][ j ];
                if ( !minL ) break; 
                rect[ i ][ j ] += minL;
            }
        }
        
        int sum = 0;
        for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= n ; ++ j )
            sum += rect[ i ][ j ];
            
        printf("%d\n",sum);
    }
    return 0;
}

zoj 2067 - White Rectangles