hdu 1510

White Rectangles

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

You are given a chessboard made up of N squares by N squares with equal size. Some of the squares are colored black, and the others are colored white. Please write a program to calculate the number of rectangles which are completely made up of white squares.

Input

There are multiple test cases. Each test case begins with an integer N (1 <= N <= 100), the board size. The following N lines, each with N characters, have only two valid character values:

# - (sharp) representing a black square;
. - (point) representing a white square.

Process to the end of file.

Output

For each test case in the input, your program must output the number of white rectangles, as shown in the sample output.

Sample Input

2 .# .. 4 ..#. ##.# .#.. .#.#

Sample Output

5 15

解题思路：这道题我一开始的想法就是先转换成01矩阵，然后再用二维树状数组判断是否能够围成一个矩形，结果TLE了。。

TLE:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char map[100][100];
int n,tree[400][400];

int lowbit(int x)
{
	return x & (-x);
}

void update(int x,int y,int d)
{
	for(int i = x; i <= n; i += lowbit(i))
		for(int j = y; j <= n; j += lowbit(j))
			tree[i][j] += d;
}

int getsum(int x,int y)
{
	int sum = 0;
	for(int i = x; i > 0; i -= lowbit(i))
		for(int j = y; j > 0; j -= lowbit(j))
			sum += tree[i][j];
	return sum;
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i = 1; i <= n; i++)
		{
			getchar();
			scanf("%s",map[i]+1);
		}
		memset(tree,0,sizeof(tree));
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(map[i][j] == '.')
					update(i,j,1);
		int ans = 0;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
			{
				for(int row = i; row >= 1; row--)
					for(int col = j; col >= 1; col--)
					{
						int sum = getsum(i,j) - getsum(i,col-1) - getsum(row-1,j) + getsum(row-1,col-1);
						int s = (i - row + 1) * (j - col + 1);
						if(s == sum) ans++;
						else break;
					}
			}
		printf("%d\n",ans);
	}
	return 0;
}

看了别人的解题报告：(有规律可循)

.   .   .   .      1  1  1  1

 .   .   .   .      2  2  2  2

 .   .   .   .      3  3  3  3

 .   .   .   .      4  4  4  4

以这种情况为例：一共有

1*4+2*4+3*4+4*4+（1）+（1+1）+（1+1+1）+（2）+（2+2）+（2+2+2）+(3)+（3+3）+(3+3+3)+(4)+(4+4)+(4+4+4)

AC:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=110;
char A[maxn][maxn];
int a[maxn][maxn];
int main()
{
    int T;
    int sum;
    while (cin>>T){
        getchar();
        sum=0;
        memset(a,0,sizeof(a));
        for(int i=0;i<T;i++){
            gets(A[i]);
            int l=strlen(A[i]);
            for(int j=0;j<l;j++){
                if(A[i][j]=='#') a[i][j]=0;
                else if(!i) a[i][j]=1;
                else a[i][j]=a[i-1][j]+1;
                sum+=a[i][j];
                if(j){
                    int ans=a[i][j];
                    for(int x=j-1;x>=0;x--){
                        if(!a[i][x]) break;
                        ans=min(ans,a[i][x]);
                        sum+=ans;
                    }
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}