题解 | #剪纸游戏#

D#剪纸游戏#

ans统计单个连通块的小正方形个数，

set<int>sx,sy记录这些小方块的横坐标，纵坐标，

如果 sx.size()*sy.size()==ans那么矩形数sum++;

#include<bits/stdc++.h>
using namespace std;
int n,m;
char g[1005][1005];
int d1[4]={0,0,-1,1};
int d2[4]={-1,1,0,0},ans=0,sum=0;
set<int>sx,sy;
void dfs(int x,int y)
{
    g[x][y]='*';
    for(int i=0;i<4;i++)
    {
        int x1=x+d1[i],y1=y+d2[i];
        if(x1>=n||y1>=m||x1<0||y1<0)
            continue;
        if(g[x1][y1]=='*')
            continue;
        sx.insert(x1),sy.insert(y1);
        ans++;
        dfs(x1,y1);
    }
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='.')
            {
                ans=1;
                sx.clear(),sy.clear();
                sx.insert(i),sy.insert(j);
                dfs(i,j);
                if(ans==sy.size()*sx.size())
                    sum++;
            }
        }
    cout<<sum;
    return 0;
}