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

题目描述
齐齐和司机在玩单机游戏《红色警戒IV》,现在他们的游戏地图被划分成一个nm的方格地图。齐齐的基地在最上方的4行格内,司机的基地在最下方的4行格内。他们只有一种攻击方式:远程大炮,相关属性如下:
1、 大炮可以打到地图的任意一个位置。
2、 双方每次必须动用本方的一门大炮攻击,齐齐先手,双方交替进行攻击。
3、 一方大炮只能攻击另一方大炮,不能攻击本方或强制攻击未获得视野的地区。
4、 被一方大炮击中的另一方大炮会产生以攻击点为中心的3
3的波及区域,波及区域内如果有其他大炮则也会产生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;
}