好久没有更新博客了,突然间想做几个贪心题目,于是就照着大黄的贪心题目分类开始刷。
题目描述的很清楚,给出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; }