$723D$ - 贝兰德的湖泊

为了解决这个问题，我们需要找出所有由点（陆地）组成的连通分量，且这些分量不与海洋有公共边界。
为此，我们需要实现深度优先搜索（DFS），并返回当前连通分量所包含的所有点的集合。

然后，我们需要将所有连通分量按照其大小递增的顺序排序，并从大小最小的分量开始，将其中的所有点（陆地）改为星号（即变为陆地），直到剩余的连通分量数量等于 $k$。

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

const int N = 55;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int n, m, k;
char g[N][N];
bool vis[N][N];
vector<pair<int, int>> border_cells; // 用于从边界开始的BFS

// 判断是否在边界上
bool onBorder(int x, int y) {
    return x == 1 || x == n || y == 1 || y == m;
}

// 从 (sx, sy) 开始 BFS 收集所有连通的水域坐标
vector<pair<int, int>> bfs(int sx, int sy, bool mark_visited = true) {
    vector<pair<int, int>> comp;
    queue<pair<int, int>> q;
    if (mark_visited) vis[sx][sy] = true;
    q.push({sx, sy});
    comp.push_back({sx, sy});

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (g[nx][ny] != '.') continue;
            if (mark_visited && vis[nx][ny]) continue;
            if (mark_visited) vis[nx][ny] = true;
            q.push({nx, ny});
            comp.push_back({nx, ny});
        }
    }
    return comp;
}

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

    // 步骤1：标记所有与海洋相连的水域（从边界开始BFS）
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (onBorder(i, j) && g[i][j] == '.' && !vis[i][j]) {
                bfs(i, j, true); // 标记它们，表示不是湖泊
            }
        }
    }

    // 步骤2：找出所有真正的湖泊（内部的水域连通分量）
    vector<tuple<int, vector<pair<int, int>>>> lakes; // size, cells
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == '.' && !vis[i][j]) {
                auto cells = bfs(i, j, true);
                lakes.emplace_back(cells.size(), cells);
            }
        }
    }

    // 步骤3：按湖泊大小从小到大排序
    sort(lakes.begin(), lakes.end());

    // 步骤4：从最小的湖泊开始填埋，直到剩下 k 个湖泊
    int filled = 0;
    int need_remove = (int)lakes.size() - k;
    for (int idx = 0; idx < need_remove; ++idx) {
        auto [sz, cells] = lakes[idx];
        for (auto [x, y] : cells) {
            g[x][y] = '*';
            ++filled;
        }
    }

    // 输出结果
    cout << filled << '\n';
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << g[i][j];
        }
        cout << '\n';
    }

    return 0;
}