Description

齐齐和司机在玩单机游戏《红色警戒IV》，现在他们的游戏地图被划分成一个的方格地图。齐齐的基地在最上方的4行格内，司机的基地在最下方的4行格内。他们只有一种攻击方式：远程大炮，相关属性如下：
1、 大炮可以打到地图的任意一个位置。
2、 双方每次必须动用本方的一门大炮攻击，齐齐先手，双方交替进行攻击。
3、 一方大炮只能攻击另一方大炮，不能攻击本方或强制攻击未获得视野的地区。
4、 被一方大炮击中的另一方大炮会产生以攻击点为中心的的波及区域，波及区域内如果有其他大炮则也会产生3*3的波及区域。
5、 两方的基地相距很远，所以不存在攻打敌方大炮时波及到本方大炮的情况。
齐齐偷偷开了“间谍卫星”，所以他能看到司机的大炮部署，司机则无视野。但如果齐齐做出攻击，司机会立即获取到发动攻击的大炮的视野，并在回合开始时动用大炮（如果存在的话）将其摧毁（摧毁后可能产生的连锁不计入视野）。
现在给出齐齐和司机的大炮部署，问齐齐在选择最优的策略下，在摧毁所有司机的大炮后可以保留最多几门本方大炮。

Solution

显然, 大炮的攻击会影响一个 的范围, 范围里面如果有大炮会继续递归上述操作下去, 那么这就是连通块的性质了
我们处理出小齐的图连通块数和每个连通块里有多少个大炮, 丢到
司机的图连通块数和每个连通块里有多少个大炮, 丢到
一次攻击只能减少一个连通块, 要想最终剩下的大炮数最少, 肯定是先用小连通块的大炮去攻击,
因此. 如果 显然输出
否则我们把连通块大小排个序, 从小的开始用， 一共要用 个
注意我的代码里 先输入了 (司机), 再输入 (小齐)
而且一定要先判断 情况, 看到有的同学写了两个 函数
其实可以把图作为参数, 这样只需要写一个函数, 大概算是模块化的思想吧(我比较懒)

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 1e6 + 5;

int m;
char maze1[5][105], maze2[5][105];
bool vis[5][105];
int dist[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, -1, -1, 1, 1, -1, 1, 1, -1};
int cur;
void dfs(int x, int y, char maze[][105]) {
  cur++;
  for(int i = 0; i < 8; i++) {
    int xx = x + dist[i][0];
    int yy = y + dist[i][1];
    if(!vis[xx][yy] && xx <= 4 && yy <= m && xx >= 1 && yy >= 1 && maze[xx][yy] == '*') {
      vis[xx][yy] = 1;
      dfs(xx, yy, maze);
    }
  }
}
vector<int> solve(char maze[][105]) {
  memset(vis, 0, sizeof(vis));
  vector<int> v;
  for(int i = 1; i <= 4; i++) {
    for(int j = 1; j <= m; j++) {
      if(!vis[i][j] && maze[i][j] == '*') {
        cur = 0;
        vis[i][j] = 1;
        dfs(i, j, maze);
        v.push_back(cur);
      }
    }
  }
  return v;
}
int main() {
  cin.ios::sync_with_stdio(false), cin.tie(nullptr);
  cin >> m; 
  for(int i = 1; i <= 4; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> maze2[i][j];
    }
  }
  for(int i = 1; i <= 4; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> maze1[i][j];
    }
  }
  vector<int> v1 = solve(maze1); // 注意这是小齐
  vector<int> v2 = solve(maze2); // 注意这是司机
  sort(v1.begin(), v1.end());
  int sum = 0;
  for(int i = 0; i < v1.size(); i++) sum += v1[i];
  if(v1.size() < v2.size()) {
    cout << -1 << "\n";
  } else {
    for(int i = 0; i < v2.size() - 1; i++) sum -= v1[i];
    cout << sum << "\n";
  }
  return 0;
}