[每日一题]模拟战役

题意

给定一张地图，表示我方和敌方2个人的地形布局，大炮间互相攻击，并且会影响3*3的区域，并且可以连带，问如果要摧毁所有敌方的大炮后，最多可以保留多少自己的大炮。

solution

分别对我方和敌方进行dfs求联通块数量，如果我方联通块更少，肯定输，输出-1。否则我们就用大炮数量最少联通块的去打对面的，这样能保证我们每次损失的大炮数量最少，敌方有b个联通块，因为我们先手，所以也只能打掉我们b-1个联通块，排序算第b-a大联通块大炮数量和就行。

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

int m;
char mp[20][105];
int vis[20][105];
int cnt;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
vector<int> v;

void dfs(int x, int y) {
  for (int i = 0; i < 8; i++) {
    int fx = x + dx[i];
    int fy = y + dy[i];
    if (!vis[fx][fy] && mp[fx][fy] == '*') {
      cnt++;
      vis[fx][fy] = 1;
      dfs(fx, fy);
    }
  }
}

int main() {
  scanf("%d", &m);
  for (int i = 1; i <= 4; i++) scanf("%s", mp[i] + 1);
  for (int i = 11; i <= 14; i++) scanf("%s", mp[i] + 1);

  int cnt1 = 0, cnt2 = 0;
  for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= m; j++) {
      if (!vis[i][j] && mp[i][j] == '*') {
        vis[i][j] = 1;
        cnt1++;
        dfs(i, j);
      }
    }
  }
  for (int i = 10; i <= 14; i++) {
    for (int j = 1; j <= m; j++) {
      if (!vis[i][j] && mp[i][j] == '*') {
        cnt = 1;
        vis[i][j] = 1;
        cnt2++;
        dfs(i, j);
        v.push_back(cnt);
      }
    }
  }
  sort(v.begin(), v.end(), greater<int>());
  if (cnt2 < cnt1)
    printf("-1\n");
  else {
    while (--cnt1) v.pop_back();
    int sum = 0;
    for (int i : v) sum += i;
    printf("%d\n", sum);
  }
  return 0;
}