题目

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

输入描述：
第1行输入一个整数m，表示地图的宽度。
第2-5行，每行输入一串长度为m的字符串，代表司机的大炮部署。（大炮为"*"号，空地为“.”号）
第6-9行，每行输入一串长度为m的字符串，代表齐齐的大炮部署。（大炮为"*"号，空地为“.”号）
数据保证：0<m≤100

输出描述：
输出一行，一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮，则输出-1。

解析

这道题我们可以从连锁效应里面发现，这道题肯定和连锁有关：dfs / bfs / 并查集。
我们简单来讲一下这三个方法的思路。

首先，我们来讲一下这道题的整体思路。
  1. 因为无论是dfs / bfs / 并查集，都是用来进行区块绑定的（这里的区块绑定就是查找连通块）。
  2. 这道题，由于敌方的炮击一炮可以干掉我们这边一个连通块。我们这边一炮也可以干掉敌方的一个连通块。

那么，我们先来了解一下我们的题目：
  1. 我们的题目说：我们先手开炮，我们的目标是干掉对方的所有炮台。而我们开炮的炮台会在下一回合被攻击。求我们最后最多可以剩下多少个炮台。
  2. 也就是说这我们剩下的炮台数完全是由我们控制的。
  3. 那么我们就知道了，按照我们的贪心思想，我们当然要每次让连通块炮台最小的炮台进行攻击
    （因为我们攻击对方次数一定，但是对方攻击我们却对我们的答案，也就是剩余炮台数目有影响）。
  4. 所以，我们只要把自己的连通块中最大的数个连通块的炮台数目加起来就是我们的答案了。

所以我们在方法的上的分歧，也就是在求连通块上的分歧：那么，我们就讲一下不同的方法：

bfs / dfs：
  1. 深度优先遍历和广度优先遍历都是查找附近的八个点。
  2. 如果碰到炮台，我们就加入栈或队列（查找到的点就做一个标记），然后继续进行遍历。
  3. 在遍历的过程中记下这个连通块的个数。
  4. 以上都是对于后手（司机）的分析，我们对先手（我们）只要加一个：记录下每个连通块的炮台数量。

并查集也差不多：
  1. 并查集也是查找附近的八个点。
  2. 先将每个节点的父亲设置为自己，如果遇到炮塔，就将找到的跑台的父亲设置为他。
  3. 然后，我们在合并炮台区块的时候，就顺便把每个区块的大小记录下来
    （最开始每个区块都是1，然后用根节点储存子树的大小，因为并查集的储存方式就是树嘛。转移的时候就把某棵树的根大小加到另一棵树的根上就行了）。
  4. 最后所以炮台中父节点等于自己的节点数，当然就是连通块的个数了（听说在一开始用路径压缩会很舒服哦）。

打代码咯（我们这里采用并查集解法）：
  1. 我们先储存好变量。
  2. 然后初始化数组：将父亲设置为自己，连通块大小设置为1。
  3. 然后按照我们上面，讲的方法，进行操作。
  4. 最后就是判断输出。如果连通块是我方少，不可能干掉对面，就是输出-1。
  5. 然后我们将连通块大小排个序，输出最大的那一部分，就是（敌方连通块数量->自己连通块数量）。
  6. 最后的最后的最后，看代码趴~

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e2 + 7;
int fa[8 * MAX], d[8 * MAX];
int way[8][2] = { {1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1} };
string s[8];
//全局变量区

int get(int x);//查找父节点+路径压缩
void merge(int x, int y);//合并
//函数预定义区

int main() {
    IOS;
    int m; cin >> m;
    for (int i = 0; i < 8; i++) {
        cin >> s[i];
        for (int j = 0; j < m; j++) {
            fa[i * m + j] = i * m + j;
            d[i * m + j] = 1;
        }
    }
    //输入数据
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < m; j++)
            if ('*' == s[i][j])
                for (int k = 0; k < 8; k++) {
                    int x = i + way[k][0];
                    int y = j + way[k][1];
                    if ((x >= 0 && x <= 3 && i <= 3) || (x >= 4 && x <= 7 && i >= 4))
                        //x在范围内
                        if (y >= 0 && y <= m - 1)
                            if ('*' == s[x][y])
                                merge(x * m + y, i * m + j);
                }
    int dirver = 0, qiqi = 0;
    int num[MAX]; memset(num, 0, sizeof num);
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < m; j++)
            if ('*' == s[i][j] && fa[i * m + j] == i * m + j)
                if (i <= 3) dirver++;
                else num[qiqi++] = d[i * m + j];
    if (qiqi < dirver) {
        cout << -1 << endl;
        return 0;
    }
    sort(num, num + qiqi);
    int ans = 0;
    for (int i = dirver - 1; i <= qiqi - 1; i++)
        ans += num[i];
    cout << ans << endl;
    return 0;
}
int get(int x) {
    return x == fa[x] ? x : fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    x = get(x); y = get(y);
    if (x != y) {
        fa[x] = y;
        d[y] += d[x];
    }
}
//函数区