White Rectangles-蒲公英云

White Rectangles

Bertha 。 2022-06-17 05:59 189阅读 0赞

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

题意：地图中找出由点构成的矩形的个数

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
char a[110][110];
int coun[110][110];
int n;
void A()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]=='.')
            coun[i][j]=coun[i][j-1]+1;
            //printf("%d ",coun[i][j]);
        }
        //printf("\n");
/*
1 2 0 1
0 0 1 0
1 0 1 2
1 0 1 0
*/
    }
}
int AA()
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)//
        {
            int m=inf;
            for(int l=i;l<=n&&coun[l][j]!=0;l++)//1列1列的判断,点不连续就结束
            {
                m=min(m,coun[l][j]);
                ans+=m;
            }
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(coun,0,sizeof(coun));
        for(int i=1;i<=n;i++)
            scanf("%s",a[i]+1);
        A();
        printf("%d\n",AA());
    }
    return 0;
}