题目大意

两方玩游戏，每次都会使用己方的大炮攻击对方，会产生以攻击点为中心的3*3的波及区域，求我们最多能保留多少大炮并且将对方的大炮消耗完

解题思路

因为我们用大炮攻击对方时，对方就会获得我们这枚大炮的视野，所以我们要尽量用连通块中数量较少的大炮去攻击对方

#include<bits/stdc++.h>
using namespace std;
int m;
char qq[5][110];
char sj[5][110];
int dx[]={-1,1,0,0,-1,-1,1,1};
int dy[]={0,0,-1,1,-1,1,-1,1};
bool vis[5][110];

int bfs(char a[][110],int x,int y){
    int cnt=1;
    vis[x][y]=1;
    queue<pair<int,int>>q;
    q.push({x,y});
    while(!q.empty()){
        pair<int,int> it=q.front(); q.pop();
        for(int i=0;i<8;++i){
            int nx=it.first+dx[i]; 
            int ny=it.second+dy[i]; 
            if(nx>=1&&nx<=4&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='*'){
                vis[nx][ny]=1;
                q.push({nx,ny});
                cnt++;
            }
        }
    }
    return cnt;
}

int main(){
    cin>>m;
    
    for(int i=1;i<=4;++i){
        for(int j=1;j<=m;++j){
            cin>>sj[i][j];
        }
    }
    memset(vis,0,sizeof(vis));
    int k=0;
    for(int i=1;i<=4;++i){
        for(int j=1;j<=m;++j){
            if(sj[i][j]=='*'&&!vis[i][j]){
                k++; //我们仅需要记录司机有多少个大炮
                bfs(sj,i,j);
            }
        }
    }
    
    for(int i=1;i<=4;++i){
        for(int j=1;j<=m;++j){
            cin>>qq[i][j];
        }
    }
    memset(vis,0,sizeof(vis));
    int sum=0;
    vector<int>liantong;
    
    for(int i=1;i<=4;++i){
        for(int j=1;j<=m;++j){
            if(qq[i][j]=='*'&&!vis[i][j]){
                int t=bfs(qq,i,j); //t记录的是这个点的大炮的连通块中有多少个大炮
                sum+=t; //sum连加记录总共有多少个大炮
                liantong.push_back(t);
            }
        }
    }
    if(liantong.size()<k) cout<<-1<<endl;
    else{
        sort(liantong.begin(),liantong.end());
        for(int i=0;i<k-1;++i) //合并成k个连通块 总共需要合并k-1次
            sum-=liantong[i];
        cout<<sum<<endl;
    }
    
    return 0;
}