搜索、贪心

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

分析

本题中，我们可以把大炮分为一个个连通块。因为3x3的性质使他们一个被炸全部死亡。
所以，齐齐与司机之间的战役其实是齐齐不断拿一个连通块去换司机的一个连通块。
既然如此，齐齐当然要从大炮最少的连通块开始去和司机换。
这样，剩下的连通块中大炮门数的总和就一定是齐齐最终能剩下的大炮门数。
而如果齐齐的连通块数小于司机的连通块数，那么齐齐就无法打败司机了
注意一点，假设齐齐有连通块n个，司机有m个
那么剩下的大炮门数应为是从m-1一直加到n，注意不是从m（因为齐齐先手）
在这里存在一个特判！当m为0时要特判一下，否则数组出界。
代码如下、注意细节

#include<iostream>;
#include<algorithm>;
#include<vector>;
using namespace std;
typedef pair<int, int> pii;
const int max_m = 110;
int m;
vector<int> a;
vector<int> b;
char q[4][max_m];
char s[4][max_m];
int dir[8][2] = { {1,1},{1,0}, {1,-1},{0,1},{0,-1},{-1,0},{-1,-1},{-1,1} };

void Search(vector<int>& a,char q[][max_m]) {
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j <= m;j++) {
            if (q[i][j] == '*') {
                a.push_back(0);
                q[i][j] = '.';
                vector<pii> tmp = { {i,j} };
                while (!tmp.empty()) {
                    a.back()++;
                    pii p = tmp.back();tmp.pop_back();
                    for (int k = 0;k < 8;k++) {
                        int x = p.first + dir[k][0];
                        int y = p.second + dir[k][1];
                        if (x >= 4 || x < 0 || y >= m || y < 0)continue;
                        if (q[x][y] == '*') {
                            q[x][y] = '.';
                            tmp.push_back(pii(x, y));
                        }
                    }
                }
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin >> m;
    for (int i = 0;i < 4;i++)
        for (int j = 0;j < m;j++)
            cin >> s[i][j];
    for (int i = 0;i < 4;i++)
        for (int j = 0;j < m;j++)
            cin >> q[i][j];
    Search(a, q);Search(b, s);
    sort(a.begin(), a.end());
    if (a.size() < b.size())
        cout << -1 << endl;
    else {
        int ans = 0;
        for (int i = max(0,(int)b.size() - 1);i < a.size();i++)
            ans += a[i];
        cout << ans << endl;
    }
}