今天的每日一题比较简单。

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

输入描述:
第1行输入一个整数m，表示地图的宽度。
第2-5行，每行输入一串长度为m的字符串，代表司机的大炮部署。（大炮为"*"号，空地为“.”号）
第6-9行，每行输入一串长度为m的字符串，代表齐齐的大炮部署。（大炮为"*"号，空地为“.”号）
数据保证：0<m≤100
输出描述:
输出一行，一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮，则输出-1。

思路：
由题意可知，每个大炮如果被攻击了，就会引发一系列的蝴蝶效应，以该门大炮为中心的3 * 3方阵内的大炮也会被破坏掉。
那么只需要分别对齐齐和司机的游戏地图，进行一次dfs，算出来每个人的连通块。
如果齐齐的大炮的连通块＜司机大炮的连通块，那么就输出-1
否则的话，根据贪心思想，齐齐每次应该用连通块内大炮数量最小的个数去打司机的，打司机的哪个联通块我们并不在乎，因为一定要打完。假设齐齐有a个联通块，司机有b个，且a>=b,那么剩余的大炮数量，即是将齐齐的联通块从小到大排序后，从第b个加到第a个。(司机有b个连通块，但齐齐先手，所以司机只能打掉齐齐b-1个连通块)

#include<bits/stdc++.h>
using namespace std;
char mp[10][105];
int m;
int ans1[405],ans2[405];
int num;
int to[][2]={1,0,-1,0,0,1,0,-1,-1,-1,-1,1,1,-1,1,1};
void dfs(int x,int y,int k){
    if(mp[x][y]=='.')  return ;
    mp[x][y]='.',++num;
    for(int i=0;i<8;i++){
        int fx=x+to[i][0],fy=y+to[i][1];
        if(fx>=0+k&&fx<4+k&&fy>=0&&fy<m){
            dfs(fx,fy,k);
        }
    }
}
int main(){
    cin>>m;
    for(int i=0;i<8;i++) cin>>mp[i];
    for(int i=0;i<4;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='*'){
                num=0;
                dfs(i,j,0);
                ans1[++ans1[0]]=num;
            }
        }
    }

    for(int i=4;i<8;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]=='*'){
                num=0;
                dfs(i,j,4);
                ans2[++ans2[0]]=num;
            }
        }
    }
    if(ans1[0]>ans2[0]) cout<<-1;
    else{
        sort(ans2+1,ans2+ans2[0]+1);
        int ans=0;
        for(int i=ans1[0];i<=ans2[0];i++){
            ans+=ans2[i];
        }
        cout<<ans;
    }
    return 0;
}