2013
12-12

# White Rectangles

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.

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.

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

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

5
15

#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;
}