题意：

齐齐和司机各有一个 的矩阵表示各自的方格地图。格子内可能会有 '*' 表示大炮。
齐齐先手攻击，选择一个大炮攻击司机的大炮。被击中的大炮会产生 的波及区域。被波及的大炮会接着产生波及区域。齐齐选择的的大炮在攻击后会暴露视野，意味着接下来会被司机攻击（如果司机还存在大炮的话）。
问齐齐在消灭了司机所有大炮，最多可保留的大炮数量。

解法：

并查集 / DFS / BFS + 贪心。

  • 将每个大炮和其相邻（ 范围内）的大炮做成一个连通块。那么齐齐选择一个连通块中的任一门大炮和攻击司机的任一连通块中的任一门大炮，效果是一样的。因此可以用并查集 / DFS / BFS 求出所有连通块，以及每个连通块的数量（即大炮门数）。

  • 记司机包含的连通块数量为 ，若 ，则齐齐可以保留所有大炮。若 ，那么齐齐的前 次攻击的大炮都会被摧毁。那么我们可以贪心地选择数量最少的 个连通块去攻击，然后被摧毁。剩下的大炮就可以保留了。

Code：

#include <bits/stdc++.h>
using namespace std;
char s[5][105], t[5][105];
bool vis[5][105];
int n = 4, m;
int dfs(char c[][105], int x, int y) {
    if(x < 1 || x > 4 || y < 1 || y > m || vis[x][y] || c[x][y] != '*') return 0;
    vis[x][y] = 1;
    int res = 1;
    for(int i = -1; i <= 1; i++)
        for(int j = -1; j <= 1; j++)
            res += dfs(c, x + i, y + j);
    return res;
}
vector<int> get(char c[][105]) {
    memset(vis, 0, sizeof vis);
    vector<int> res;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!vis[i][j] && c[i][j] == '*') {
                res.push_back(dfs(c, i, j));
            }
    return res;
}
int main() {
    cin >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> s[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> t[i][j];
    vector<int> sv = get(s), tv = get(t);
    sort(tv.begin(), tv.end());
    if(sv.size() > tv.size()) cout << -1 << endl;
    else {
        int ans = 0;
        for(int i = max(0, (int)sv.size() - 1); i < tv.size(); i++) ans += tv[i];
        cout << ans << endl;
    }
    return 0;
}