题解 | #画圈游戏#

将整个棋盘分为横坐标与纵坐标的和为奇数和偶数的两种，此时，棋盘就变为了一个二分图。
仅针对和为奇数的点而言，若这个点为${}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}\text{'}*\text{'}$，如果它能匹配到邻近的也为${}^{\mathrm{\prime }}{\ast }^{\mathrm{\prime }}\text{'}*\text{'}$的点，那么cnt就加二。
cnt代表被能覆盖两个星星的牌。
而cnt_代表总的星星数。
那么最后的结果就是cnt/2+(cnt_-cnt)

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int>PII;
vector<PII>ve;
char g[105][105];
bool st[105][105];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m;
PII match[105][105];
bool find(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<1 || a>n || b<1 || b>m)
        {
            continue;
        }
        if(st[a][b])
        {
            continue;
        }
        if(g[a][b]=='o')
        {
            continue;
        }
        st[a][b]=true;
        if(match[a][b].first == -1 || find(match[a][b].first,match[a][b].second))
        {
            match[a][b]={x,y};
            return true;
        }
    }
    return false;
}
int main()
{
    cin>>n>>m;
    int cnt_=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
            match[i][j]={-1,-1};
            if(g[i][j]=='*')
            {
                cnt_++;
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((i+j)%2)
            {
                if(g[i][j]=='*')
                {
                    memset(st,false,sizeof st);
                    if(find(i,j))
                    {
                        cnt+=2;
                    }
                }
            }
        }
    }
    cout<<cnt/2+(cnt_-cnt)<<endl;
}