模拟战役：原题链接
题目描述：
齐齐和司机在玩单机游戏《红色警戒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。
思路：
这是一个连通块问题，将所有能互相炸到的大炮看作一个连通块，分别计算司机和齐齐的连通块数量，并记录齐齐每个连通块中大炮的数量。按照题意，齐齐炸掉司机的一个连通块会失去自己的这个连通块，因此按照齐齐每个连通块中大炮的数量递增排序，先用数量少的连通块炸，剩余的大炮会尽可能的多。
能否炸完司机只需比较齐齐和司机的连通块数量，若齐齐的连通块数量大于等于司机的，就能炸完，若小于，就炸不完，直接输出-1即可。
求一个连通块时用dfs，记录齐齐每个连通块中大炮的数量只需用一个数组存储即可。
代码解析：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 110;
char e1[5][N],e2[5][N]; //存两个地图
bool vis[N][N]; //标记数组
int m,cnt,sum; //m是宽度，cnt是一个连通块中大炮数量的计数变量，sum是剩余大炮数量和
vector<int> arr1,arr2; //存各个连通块中大炮的数量
int ne[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; //因为炸毁的是3*3的地方，也就相当于向8个方向扩展
void dfs(int x,int y,char e[5][N]) //dfs连接大炮形成连通块
{
cnt++; //多一个大炮计数+1
vis[x][y] = 1; //标记此大炮
for(int i = 0;i < 8;i++) //向8个方向扩展
{
int tx = x + ne[i][0];
int ty = y + ne[i][1];
if(tx < 0 || ty < 0 || tx >= 4 || ty >= m) //边界判断
continue;
if(e[tx][ty] == '*' && vis[tx][ty] == 0) //如果碰到大炮，再dfs扩展
dfs(tx,ty,e);
}
}
vector<int> cal(char e[5][N])
{
vector<int> arr; //arr来存储个连通块的大炮数量
memset(vis,0,sizeof vis); //重置vis数组
for(int i = 0;i < 4;i++)
{
for(int j = 0;j < m;j++) //遍历地图每个点
{
if(e[i][j] == '*' && vis[i][j] == 0) //如果是大炮，dfs扩展
{
cnt = 0; //重置cnt
dfs(i,j,e);
arr.push_back(cnt); //cnt入数组
}
}
}
return arr; //返回数组
}
int main()
{
cin >> m;
for(int i = 0;i < 4;i++)
for(int j = 0;j < m;j++)
cin >> e1[i][j]; //注意，此题中先输入的是司机的地图
for(int i = 0;i < 4;i++)
for(int j = 0;j < m;j++)
cin >> e2[i][j]; //e2是齐齐的地图
arr1 = cal(e1);
arr2 = cal(e2);
sort(arr1.begin(),arr1.end()); //对齐齐的各连通块中大炮的数量排序
if(arr1.size() < arr2.size()) //如果齐齐的连通块比司机的少，无法炸完，直接输出-1
cout << -1 << endl;
else
{
for(int i = arr2.size()-1;i < arr1.size();i++)
sum += arr1[i]; //如果能炸完，取炸完后，剩余的数量加和
cout << sum << endl;
}
return 0;
}