题解 | #模拟战役#

本题可以抽象为求连通块的数目，以及求每个连通块内的元素的个数,求司机大炮的连通块的个数，司机反击的次数最多只有连通块数目-1次，因为是qiqi先手，而qiqi想要使得每次开炮后被反击的代价最小，需要贪心找出最小的连通块，使用其中的大炮进行攻击

注意：连通块内元素个数的初值res要设置为1，因为要考虑搜索初始的元素

#include<bits/stdc++.h>
using namespace std;
int m;
const int M=105;
char mp[M][M];
int mov[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
int vis[M][M];
bool check(int x,int y){
	return x>=1&&x<=4&&y>=1&&y<=m;
}
bool check1(int x,int y){
	return x>=5&&x<=8&&y>=1&&y<=m;
}
void dfs(int x,int y){

	for(int i=0;i<8;i++){
		int xx=x+mov[i][0];
		int yy=y+mov[i][1];
		if(check(xx,yy)&&!vis[xx][yy]&&mp[xx][yy]=='*'){
			vis[xx][yy]=1;
			dfs(xx,yy);
		}
	}
}
int res=1;
void dfs1(int x,int y,int num){
	for(int i=0;i<8;i++){
		int xx=x+mov[i][0];
		int yy=y+mov[i][1];
		if(check1(xx,yy)&!vis[xx][yy]&&mp[xx][yy]=='*'){
			vis[xx][yy]=1;
			dfs1(xx,yy,num);
			
			res+=num;
		//	cout<<"res: "<<res<<endl;
		}
	}
}
int main(){
	cin>>m;
	for(int i=1;i<=8;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	int cnt=0;
	for(int i=1;i<=4;i++){	//求司机的连通块数目 
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='*'&&!vis[i][j]){
				vis[i][j]=1;
				dfs(i,j);
				cnt++;
			}
		}
	}
	int num[M];
	int tot=0;
	for(int i=5;i<=8;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='*'&&!vis[i][j]){
				vis[i][j]=1;
				
				dfs1(i,j,1);
				num[++tot]=res;
			//	cout<<"res:"<<" "<<res<<"   ";
				res=1;
			}
		}
	}
//	cout<<"tot: "<<tot<<endl;
	sort(num+1,num+1+tot);
	for(int i=1;i<=cnt-1;i++){
		num[i]=0;
	}
	int ans=0;
	for(int i=1;i<=tot;i++){
		ans+=num[i];
	}
	if(ans==0){
		cout<<"-1"<<endl;
	}
	else
		cout<<ans<<endl;
	return 0;
}
//20
//*....**..*..***....*
//..*..*..*.......*...
//*.....*...*..*....**
//..***..*....*...**..
//.....*..****..*.....
//*.*..*...........*..
//.......*.*..**.....*
//**..**.........*..**	11