链接：https://ac.nowcoder.com/acm/problem/14698
来源：牛客网

题目描述

齐齐和司机在玩单机游戏《红色警戒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。
思路：分析一下就可以发现，题目要求的就是双方的连通块数量，这个可以用BFS得出，套模板即可
然后比较连通块数量，很明显，当司机的连通块数量大于齐齐的连通块数量时，输出-1
当司机的连通块数量小于等于齐齐的连通块数量时，计算齐齐的剩余大炮数量
可以看出，应该让司机每一次的攻击都只能攻击到最小的连通块
所以可以用BFS计算每一个连通块的大小，然后存储到小根堆里面去
大致思路就是这样，用代码实现总体不难

代码如下：
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct node{
    int tmp,x,y;
};
queue<node>q;
priority_queue<int,vector<int>,greater<int>>qp1,qp2;
char mp[120][120];
int vis[120][120];
int dir[8][2]={{1,0},{1,-1},{0,1},{1,1},{-1,0},{-1,1},{0,-1},{-1,-1}};
int n,maxstep=0;
void BFS(){
    while(!q.empty()){
        node temp=q.front();
        if(temp.tmp>maxstep){
            maxstep=temp.tmp; //记录这个连通块内包含*（大炮）的数量
        }
        q.pop();
        for(int i=0;i<8;i++){
            int xx=temp.x+dir[i][0];
            int yy=temp.y+dir[i][1];
            if(xx<0 || yy<0 || xx>=4 || yy>=n || mp[xx][yy]=='.' || vis[xx][yy]) continue;
            vis[xx][yy]=1;
            q.push(node{temp.tmp+1,xx,yy});
        }
    }
}
int main(){
    int ans1=0,ans2=0,num1=0,num2=0;
    scanf("%d",&n);
    for(auto i=0;i<4;i++){
        scanf("%s",mp[i]);
    }
    for(auto i=0;i<4;i++){
        for(auto j=0;j<n;j++){
            if(mp[i][j]=='*') num1++;
            if(!vis[i][j] && mp[i][j]=='*'){
                vis[i][j]=1;
                q.push(node{1,i,j});
                ans1++;
                BFS();
                qp1.push(maxstep); //塞入小根堆中，方便后面操作
                maxstep=0;
            }
        }
    }
    memset(vis,0,sizeof(vis));
    for(auto i=0;i<4;i++){
        scanf("%s",mp[i]);
    }
    for(auto i=0;i<4;i++){
        for(auto j=0;j<n;j++){
            if(mp[i][j]=='*') num2++;
            if(!vis[i][j] && mp[i][j]=='*'){
                vis[i][j]=1;
                q.push(node{1,i,j});
                ans2++;
                BFS();
                qp2.push(maxstep); //塞入小根堆中，方便后面操作
                maxstep=0;
            }
        }
    }
    if(qp1.size()>qp2.size()){ //如果司机的连通块数量大于齐齐的连通块数量，就输出-1
        printf("-1\n");
    }else{
        while(qp1.size()>1){ //这里是1不是0！
            num2-=qp2.top();
            qp1.pop();
            qp2.pop();
        }
        printf("%d\n",num2);
    }
    return 0;
}