模拟战役（dfs，贪心）

题目：

2个4*n的图，表示后手和先手部署炮台的方案。问先手那方在消灭后手所有炮台的条件下最多能保留自己多少炮台。

做法：

先求出后手和先手炮台联通块数量和。
若，无解。
否则，由于先手每次打击后必定暴露一个联通块。我们贪心选择暴露炮塔数量少的联通块就行了。
所以先手方最多能保留最大的个联通块中的炮台数。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 110;
char s[5][N];
int n, col[5][N], color, clor_cnt;
vector<int> v;
void dfs(int x, int y){
    col[x][y] = color;
    clor_cnt++;
    for (int i = -1; i <= 1; ++i){
        for (int j = -1; j <= 1; ++j){
            if (i == 0 && j == 0) continue;
            int tx = x+i, ty = y+j;
            if (tx < 1 || tx > 4 || ty < 1 || ty > n || s[tx][ty] != '*' || col[tx][ty]) continue;
            dfs(tx, ty);
        }
    }
}
int main(void){ 
    IOS;
    cin >> n;
    for (int i = 1;  i<= 4; ++i){
        cin >> (s[i]+1);
    }
    int tgt_num = 0;
    for (int i = 1; i <= 4; ++i){
        for (int j = 1; j <= n; ++j){
            if (s[i][j] == '*' && !col[i][j]){
                color++, clor_cnt = 0;
                dfs(i, j);
                tgt_num++;
            }
        }
    }
    memset(col, 0, sizeof col);
    color = 0;
    for (int i = 1; i <= 4; ++i){
        cin >> (s[i]+1);
    }
    for (int i = 1; i <= 4; ++i){
        for (int j = 1; j <= n; ++j){
            if (s[i][j] == '*' && !col[i][j]){
                color++, clor_cnt = 0;
                dfs(i, j);
                v.push_back(clor_cnt);
            }
        }
    }
    if (v.size() < tgt_num){
        cout << -1 << endl;
    }else{
        sort(v.begin(), v.end(), greater<int>());
        int ans = 0;
        for (int i = 0; i < v.size()-tgt_num+1; ++i){
            ans += v[i];
        }
        cout << ans << endl;
    }
    return 0;
}