题意分析

给定一个 的棋盘，求放置一颗黑子后能全包围的白子极大连通块的大小总和的最大值。

题解

我们考虑放置一颗黑子对白子极大连通块包围的贡献，无论如何放置，一颗黑子对于包围的贡献只能为 。所以需要考虑的只有只差一个黑子即可达成全包围，也就是恰有一个*和.相连（四连通）的白子极大连通块。

需要注意的是，形如下列数据：

10
..........
.########.
#***#****#
#***#****#
#***.****#
#***#****#
#***#****#
#***#****#
.########.
..........

左侧和右侧的白子极大连通块均满足只差一个黑子即可达成全包围，而差的那个黑子都位于同一点。我们可以把在这里放置一个黑子可以吃掉的白子总数其视作和白子相连的那一个空点的权值，之后把每个符合要求的连通块的大小累加在缺口点处即可。

遍历连通块的过程可以用广度优先搜索（BFS）完成。

总时间复杂度

代码见下。

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
const int drs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int n;
int values[N][N];
bool vis[N][N];

bool inR(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < n; // 防越界小助手
}

array<int, 3> bfs(const vector<string>& G, const int x, const int y){
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = true;
    int siz = 0;
    set<pair<int, int>> blk; // 存储该连通块中和白子相连的空点坐标

    while(!q.empty()){
        auto [cx, cy] = q.front();
        q.pop();
        siz++;
        for(const auto& dir : drs){
            int nx = cx + dir[0], ny = cy + dir[1];
            if(inR(nx, ny)){
                if(G[nx][ny] == '*' && !vis[nx][ny]){
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }else if(G[nx][ny] == '.'){
                    blk.insert({nx, ny});
                }
            }
        }
    } // 需要注意的是，气是整个连通块共享的，且吃子也是要对整个连通块操作。不能在发现blk.size() > 1时return {-1, -1, -1}, 会导致没搜到的部分被错误得计入其他连通块内，造成WA。也可能会出现一个连通块重复搜索很多次导致TLE的情况。

    if(blk.size() == 1){ // 只压进去了一个说明只有一口气，好吃
        pair<int, int> tp;
        tp = *blk.begin();
        return {tp.first, tp.second, siz};
    }else{
        return {-1, -1, -1}; // 否则该连通块应弃置
    }
}

int main(){
    memset(values, 0, sizeof values);
    memset(vis, 0, sizeof vis); // 初始化操作
    cin >> n;
    vector<string> G(n);
    for(int i = 0; i < n; ++i){
        cin >> G[i];
    }
    
    int R = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(!vis[i][j] and G[i][j] == '*'){
                auto [x, y, sz] = bfs(G, i, j);
                if(x < 0) continue; // 非法时就下一个
                values[x][y] += sz; // 累加点权
                R = max(values[x][y], R); // 更新点权最大值，小小小小小小优化
            }
        }
    }
    cout << R << endl;
    return 0;
}