White Rectangles

Bertha 。 2022-06-17 05:59 125阅读 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;
    }