ZOJ 2067 White Rectangles (greedy)

ZOJ 2067 White Rectangles

好久没有更新博客了，突然间想做几个贪心题目，于是就照着大黄的贪心题目分类开始刷。

题目描述的很清楚，给出n*n的地图，需要找出全部由白色点组成的矩形的个数。刚开始想到的是枚举，不过这个复杂度也太高了。需要做一个预处理，需要统计处从某一点开始向右最长的连续白点个数，保存在rightt中。然后进行枚举每个点，统计以他为左上角的矩形的个数，其间还要枚举高度。。时间复杂度O(N^3)

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int main(void){
    char map[ 102 ][ 102 ];
    int rightt[ 102 ][ 102 ];
    int n,i,j,k,len,m,total;
    while( cin >> n ){
        getchar();
        for( i = 1; i <= n; i++ ){
            gets( map[i]+1 );
            for( j = 1; j <= n;j ++ )
                rightt[i][j] = 0;
        }

        for( i = 1; i <=n; i++ )
            for( j = 1; j <= n; j++ )
                if( map[i][j] == '.' ){
                    m = j;
                    while( map[i][m] == '.' )
                        rightt[i][j]++,m++;
                }//统计到右边最长的连续白点

        total = 0;
        for( i = 1; i <=n; i++ )
            for( j = 1; j <= n; j++ ) {
                len = 10086;
                for( k = i; k <= n && rightt[k][j]; k++ ){
                    len = min( len,rightt[k][j] );
                    total += len;
                }//内层这个循环是按高度枚举的
            }
        cout << total << endl;

    }
    return 0;
}