牛客小白月赛86

链接https://ac.nowcoder.com/acm/contest/73450/D 这道题直接用BFS把所有连通块找出来，将每一个连通块的最大最小的x轴与y轴坐标记录下来，遍历这四个点所包含的区域，看是否有'*'就行了，下面是代码。

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}

#define ONLINE_JUDGE

typedef pair<int,int> PII;
const int N=1010;
int n,m;
char mp[N][N];
int a[N][N];
int dir[][2]={{1,0},{-1,0},{0,-1},{0,1}};

int bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y});
    int x1=INT_MAX,x2=0,y1=INT_MAX,y2=0;
    x1=min(x1,x);
    x2=max(x2,x);
    y1=min(y1,y);
    y2=max(y2,y);
    while(!q.empty())
    {
        int dx=q.front().first;
        int dy=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ex=dx+dir[i][0];
            int ey=dy+dir[i][1];
            if(ex<1||ex>n||ey<1||ey>m||mp[ex][ey]=='*'||mp[ex][ey]=='-')
            {
                continue;
            }
            x1=min(x1,ex);
            x2=max(x2,ex);
            y1=min(y1,ey);
            y2=max(y2,ey);
            mp[ex][ey]='-';
            q.push({ex,ey});
        }
    }
    for(int i=x1;i<=x2;i++)
    {
        for(int j=y1;j<=y2;j++)
        {
            if(mp[i][j]=='*')
            {
                return 0;
            }
        }
    }
    return 1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    ios;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mp[i][j]=='.')
            {
                sum+=bfs(i,j);
            }
        }
    }
    cout<<sum<<"\n";
    return 0;
}