题解 | #公平对局#

这里有一个减少代码量的方法：

对于一个黑子挤死两块白子的情况，可以假装填入一颗白子，再丢到dfs里计算。

注意一般情况不能用这种方法去算。

这样dfs就只用维护白子的个数和气的位置。

气的位置可能会数重，所以要用map判重(unordered_map更好)。

using namespace std;
int n,m[1001][1001],ans,cnt;
bool vis[1001][1001];
int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
map<int,int> my;
void dfs(int x,int y)
{
    cnt++;//记录一块白子的总数
    vis[x][y]=1;
    for(int i=0;i<4;i++)
        if(!vis[x+fx[i]][y+fy[i]]&&x+fx[i]<=n&&x+fx[i]>=1&&y+fy[i]>=1&&y+fy[i]<=n)
        {
            if(m[fx[i]+x][fy[i]+y]==3)
                dfs(fx[i]+x,fy[i]+y);
            if(m[x+fx[i]][y+fy[i]]==1)
                my.insert(pair<int,int>(x+fx[i],y+fy[i]));//搜出一块白子的气的位置
        }
             
}
int main()
{
    char s;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>s;
            if(s=='.')m[i][j]=1;
            else if(s=='#')m[i][j]=2;
            else m[i][j]=3;
        }
    for(int i=1;i<=n;i++)//这里是第一次搜索，找到所有只剩一口气的白子
        for(int j=1;j<=n;j++)//这是第一种情况，维护最大值
            if(!vis[i][j]&&m[i][j]==3)
            {
                cnt=0;my.clear();
                dfs(i,j);
                if(my.size()==1)
                    ans=max(cnt,ans);
            }
    memset(vis,0,sizeof vis);//这里是第二次搜索，针对两块白子公用一气
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!vis[i][j]&&m[i][j]==1)//如果此处是空地
            {
                bool tag1=0;
                for(int k=0;k<4;k++)
                    if(m[i+fx[k]][j+fy[k]]==3)
                        tag1=1;
                if(!tag1)continue;//如果周围有白子
                m[i][j]=3;//如果放入白子，代入dfs计算
                cnt=0;my.clear();
                dfs(i,j);
                if(my.size()==0)
                    ans=max(cnt-1,ans);//取出白子，数量-1
                m[i][j]=1;
            }
    cout<<ans;
}