模拟战役（DFS||并查集解法）
题目描述 齐齐和司机在玩单机游戏《红色警戒IV》，现在他们的游戏地图被划分成一个nm的方格地图。齐齐的基地在最上方的4行格内，司机的基地在最下方的4行格内。他们只有一种攻击方式：远程大炮，相关属性如下： 1、 大炮可以打到地图的任意一个位置。 2、 双方每次必须动用本方的一门大炮攻击，齐齐先手，双方交替进行攻击。 3、 一方大炮只能攻击另一方大炮，不能攻击本方或强制攻击未获得视野的地区。 4、 被一方大炮击中的另一方大炮会产生以攻击点为中心的33的波及区域，波及区域内如果有其他大炮则也会产生33的波及区域。 5、 两方的基地相距很远，所以不存在攻打敌方大炮时波及到本方大炮的情况。 齐齐偷偷开了“间谍卫星”，所以他能看到司机的大炮部署，司机则无视野。但如果齐齐做出攻击，司机会立即获取到发动攻击的大炮的视野，并在回合开始时动用大炮（如果存在的话）将其摧毁（摧毁后可能产生的连锁不计入视野）。 现在给出齐齐和司机的大炮部署，问齐齐在选择最优的策略下，在摧毁所有司机的大炮后可以保留最多几门本方大炮。 输入描述: 第1行输入一个整数m，表示地图的宽度。 第2-5行，每行输入一串长度为m的字符串，代表司机的大炮部署。（大炮为"“号，空地为“.”号） 第6-9行，每行输入一串长度为m的字符串，代表齐齐的大炮部署。（大炮为”*"号，空地为“.”号） 数据保证：0<m≤100 输出描述: 输出一行，一个整数。代表摧毁所有司机的大炮后最多保留几门大炮。如果不能摧毁所有司机的大炮，则输出-1。
思路：很简单的一个联通块题目
首先，我们把同一个阵营中，会相互波及到的大炮放进一个连通块中，这样的话，很容易可以发现，如果连通块中有一个大炮被攻击了的话，那么，整个连通块的大炮都会被波及。
现在，假设我们将双方的联通块个数及大小求出来了 那么，对于齐齐来说，每次攻击就相当于用一个联通块抵消掉司机的一个联通块（最后一个不算）
那么很明显，要让剩下的大炮最多，这就是一个简单贪心问题了，我们用最小的k-1个联通块去把司机的联通块抵消的（第k个保留就行），然后，统计剩下连通块中大炮的数量之和即为答案。
而如果t<k,那么，齐齐的联通块就不能够抵消掉司机的所有联通块，输出-1即可
至于实现的话，我们可以用bfs或者并查集实现。
并查集版本
#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<=4)||(i>4&&x>4&&x<=8))&&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;
}DFS版本
#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;
}