题解 | 剪纸游戏

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
const ll INF = 1e18;
int n,m;
char b[N][N];
bool vis[N][N];

ll dir[4][2] = {1,0,0,1,-1,0,0,-1};
bool ok;
ll xmn,ymn,xmx,ymx;
void dfs(ll x,ll y)
{

    for(int i=0;i<=4;i++)
    {
        ll cx = x+dir[i][0];
        ll cy = y+dir[i][1];
        if(cx<=0||cy<=0||cx>n||cy>m)continue;
        if(vis[cx][cy]||b[cx][cy]=='*')continue;
        vis[cx][cy]=true;
        xmx = max(xmx,cx);
        ymx = max(ymx,cy);
        xmn = min(xmn,cx);
        ymn = min(ymn,cy);
        dfs(cx,cy);
    }

}


bool check()
{
    // cout<<xmn<<' '<<ymn<<' '<<xmx<<' '<<ymx<<'\n';
    for(int i=xmn;i<=xmx;i++)
    {
        for(int j=ymn;j<=ymx;j++)
        {
            if(b[i][j]=='*')return false;
        }
    }
    return true;
}

void solve()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>b[i][j];
        }
    }

    ll cnt = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(vis[i][j])continue;
            if(b[i][j]=='*')continue;
            vis[i][j]=true;
            xmx = i,ymx =j;
            xmn = i,ymn=j;
            dfs(i,j);
            if(check())cnt++;
        }
    }

    cout<<cnt<<'\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    while(t--)
    {
        solve();
    }


    return 0;
}