很简单的一个联通块题目

首先，我们把同一个阵营中，会相互波及到的大炮放进一个连通块中，这样的话，很容易可以发现，如果连通块中有一个大炮被攻击了的话，那么，整个连通块的大炮都会被波及。

现在，假设我们将双方的联通块个数及大小求出来了，分别为：

司机:

齐齐:

那么，对于齐齐来说，每次攻击就相当于用一个联通块抵消掉司机的一个联通块（最后一个不算）

那么很明显，要让剩下的大炮最多，这就是一个简单贪心问题了，我们用最小的k-1个联通块去把司机的联通块抵消的（第k个保留就行），然后，统计剩下连通块中大炮的数量之和即为答案。

而如果t<k,那么，齐齐的联通块就不能够抵消掉司机的所有联通块，输出-1即可

至于实现的话，我们可以用bfs或者并查集实现。

bfs版本：
代码:

#include<bits/stdc++.h>
using namespace std;
const int N=101;
char a[N][N];int tim,m;
bool vis[N][N];int sav[N*N],e;
int dx[8]={0,0,1,-1,1,-1,1,-1};
int dy[8]={1,-1,0,0,1,-1,-1,1};
inline void bfs1(int X,int Y){
    queue<pair<int,int> >s;
    s.push(make_pair(X,Y));
    vis[X][Y]=1;
    while(!s.empty()){
        int x=s.front().first,y=s.front().second;s.pop();
        for(int i=0;i<8;++i){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx&&xx<=4&&yy&&yy<=m){
                if(!vis[xx][yy]&&a[xx][yy]=='*'){
                    vis[xx][yy]=1;s.push(make_pair(xx,yy));
                }
            }
        }
    }
}
inline int bfs2(int X,int Y){
    queue<pair<int,int> >s;
    s.push(make_pair(X,Y));
    vis[X][Y]=1;int ans=0;
    while(!s.empty()){
        int x=s.front().first,y=s.front().second;s.pop();++ans;
        for(int i=0;i<8;++i){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>4&&xx<=8&&yy&&yy<=m){
                if(!vis[xx][yy]&&a[xx][yy]=='*'){
                    vis[xx][yy]=1;s.push(make_pair(xx,yy));
                }
            }
        }
    }
    return ans;
}
int main(){
    scanf("%d",&m);
    for(int i=1;i<=8;++i){
        for(int j=1;j<=m;++j){
            scanf(" %c",&a[i][j]);
        }
    }
    for(int i=1;i<=4;++i){
        for(int j=1;j<=m;++j){
            if(!vis[i][j]&&a[i][j]=='*'){
                ++tim;bfs1(i,j);
            }
        }
    }
    for(int i=5;i<=8;++i){
        for(int j=1;j<=m;++j){
            if(!vis[i][j]&&a[i][j]=='*'){
                sav[++e]=bfs2(i,j);
            }
        }
    }
    if(e<tim){
        puts("-1");
        return 0;
    }
    sort(sav+1,sav+e+1);
    int res=0;
    for(int i=tim;i<=e;++i){
        res+=sav[i];
    }
    printf("%d",res);
    return 0;
}

并查集版本：

#include<bits/stdc++.h>
using namespace std;
const int N=101;
char a[N][N];
int dx[8]={0,0,1,-1,1,-1,1,-1};
int dy[8]={1,-1,0,0,1,-1,-1,1};
int fa[N*N],siz[N*N],m,sav[N*N],e,t;
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
    int a=find(x),b=find(y);
    if(a!=b){
        fa[a]=b,siz[b]+=siz[a];
    }
}
int main(){
    scanf("%d",&m);
    for(int i=1;i<=8;++i){
        for(int j=1;j<=m;++j){
            scanf(" %c",&a[i][j]);fa[(i-1)*m+j]=(i-1)*m+j,siz[(i-1)*m+j]=1;
        }
    }
    for(int i=1;i<=8;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]=='*'){
                for(int k=0;k<8;++k){
                    int x=i+dx[k],y=j+dy[k];
                    if(((i<=4&&x&&x<=4)||(i>4&&x>4&&x<=8))&&y&&y<=m){
                        if(a[x][y]=='*'){
                            merge((x-1)*m+y,(i-1)*m+j);
                        }
                    }
                }
            }
        }
    }
    for(int i=1;i<=8;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]=='*'&&fa[(i-1)*m+j]==(i-1)*m+j){
                if(i<=4){
                    ++t;
                }else{
                    sav[++e]=siz[(i-1)*m+j];
                }
            }
        }
    }
    if(e<t){
        puts("-1");
        return 0;
    }
    sort(sav+1,sav+e+1);
    int res=0;
    for(int i=t;i<=e;++i){
        res+=sav[i];
    }
    printf("%d",res);
    return 0;
}