传送门

简单题意

一张的地图，表示齐齐 和 司机 2个人的地形布局，一门大炮可以大对方的大炮，并且会影响3*3的区域，如果区域内同样有大炮，则继续受影响，问齐齐如果要摧毁所有司机的大炮后，最多可以保留多少自己的大炮。

分析

我们可以按照题意求出每个大炮受到影响的范围，本题中即是连通块的个数 和 大小。
设司机有个连通块，齐齐有个连通块，那么，对于齐齐来说，每次攻击就相当于用一个联通块抵消掉司机的一个联通块（最后一个不算）
要让剩下的大炮最多，我们可以贪心的考虑，我们用最小的个联通块去把司机的联通块抵消的（第k个保留就行），然后，统计剩下连通块中大炮的数量之和即为答案。

参考代码

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int m;
char mp[10][maxn];
int vis[10][maxn];
bool check(int x, int y) {
    if (x <= 0 || x > 8 || y <= 0 || y > m) return false;
    return true;
}
int n1 = 0, n2 = 0;

void dfs1(int x, int y) {
    vis[x][y] = 1;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (!i && !j) continue;
            int tx = x + i, ty = y + j;
            if (check(tx, ty) && !vis[tx][ty] && mp[tx][ty] == '*' && tx <= 4) {
                dfs1(tx, ty);
            }
        }
    }
}

void dfs2(int x, int y) {
    n2++;
    vis[x][y] = 1;
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            if (!i && !j) continue;
            int tx = x + i, ty = y + j;
            if (check(tx, ty) && !vis[tx][ty] && mp[tx][ty] == '*' && tx > 4) {
                dfs2(tx, ty);
            }
        }
    }
}

int main(void) {
    FAST_IO;

    cin >> m;
    for (int i = 1; i <= 8; i++) {
        cin >> mp[i] + 1;
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '*' && vis[i][j] == 0) {
                n1++;
                dfs1(i, j);
            }
        }
    }
    vector<int> v;
    for (int i = 5; i <= 8; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '*'  && vis[i][j] == 0) {
                n2 = 0;
                dfs2(i, j);
                v.emplace_back(n2);
            }
        }
    }
    if (n1 > v.size()) {
        cout << -1 << endl;
    } else {
        sort(v.rbegin(), v.rend());
        int ans = 0;
        for (int i = 0; i < (int)v.size() - n1 + 1; i++) {
            ans += v[i];
        }
        cout << ans << endl;
    }

    return 0;
}