White Rectangles
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 732 Accepted Submission(s): 368
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
Author
JIANG, Ming
Source
ZOJ Monthly, January 2004
Recommend
xhd
Enrich my knowledge again.In English ,left corner means the corner on the left and up side of a rectangle,and bottom left means the left and down side of a rectangle,and right side as well.It seems that the word "corner" contains the significance of up side.
Enumerate the left corner of the rectangles ,just count it.
#include<stdio.h> #include<string.h> int f[125][125]; char ch[125][125]; int main() { int n,i,j; while (scanf("%d",&n)!=EOF) { for (i=1;i<=n;i++) scanf("%s",&ch[i][1]); memset(f,0,sizeof(f)); int ans=0; for (i=1;i<=n;i++) for (j=n;j>=1;j--) if (ch[i][j]=='.') f[i][j]=f[i][j+1]+1; for (i=1;i<=n;i++) for (j=1;j<=n;j++) { int maxlen=f[i][j],v=0; while (maxlen) { ans+=maxlen; v++; if (f[i+v][j]<maxlen) maxlen=f[i+v][j]; } } printf("%d ",ans); } return 0; }