刷题记录:牛客NC14698模拟战役

传送门:牛客

题目描述:

齐齐和司机在玩单机游戏《红色警戒IV》，现在他们的游戏地图被划分成一个n*m的方格地图。齐齐的基地在最上方的4行格内，司机的基地在最下方的4行格内。他们只有一种攻击方式：远程大炮，相关属性如下：
1、    大炮可以打到地图的任意一个位置。
2、    双方每次必须动用本方的一门大炮攻击，齐齐先手，双方交替进行攻击。
3、    一方大炮只能攻击另一方大炮，不能攻击本方或强制攻击未获得视野的地区。
4、    被一方大炮击中的另一方大炮会产生以攻击点为中心的3*3的波及区域，波及区域内如果有其他大炮则也会产生3*3的波及区域。
5、    两方的基地相距很远，所以不存在攻打敌方大炮时波及到本方大炮的情况。
齐齐偷偷开了“间谍卫星”，所以他能看到司机的大炮部署，司机则无视野。但如果齐齐做出攻击，司机会立即获取到发动攻击的大炮的视野，并在回合开始时动用大炮（如果存在的话）将其摧毁（摧毁后可能产生的连锁不计入视野）。
现在给出齐齐和司机的大炮部署，问齐齐在选择最优的策略下，在摧毁所有司机的大炮后可以保留最多几门本方大炮。
输入:
3
...
.*.
..*
*..
*..
.**
...
*.*
输出:
4

感觉这道题的思路并不是很难,但是我却做的十分麻烦??

主要思路:

1. 首先看完这道题,我们发现因为这个波及范围的原因,所以假设我们有很多个点都因为波及范围的原因捆绑在一起,那么只要这几个点之中的任何一个被击中,那么显然的这整个团体也就会被一起击中.
2. 那么对于如何求出每一个小团体呢.我们可以使用搜索和并查集两种方法.如果使用的是搜索的话,就是对于每一个是大炮的点,我们根据这个点继续进行搜索,碰到大炮就继续搜索,一直到搜完一个联通块为止.如果是使用并查集的话就是碰到每一个点只要关注这个点周围的情况就行了,不用继续搜索下去.在这道题中两种方法都是可以的.
3. 对于每一个求出的小团体,我们只要齐齐的团体以个数从小到大排列即可,假设齐齐的数量小于对面的,那么显然就是无法全部击完的,输出-1即可.反之我们只要去掉敌人的大炮的数量-1(因为我们是先进行攻击的)

因为前不久才复习完并查集,因此下面的代码我们采用了带权的并查集的实现方式(因为我没有采用函数引用二维数组的方法,因此代码量比较大,但是是大量重复的)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
char mp1[100][200];
char mp2[100][200];
int m;
int fa1[maxn];
int fa2[maxn];
int cnt1=0,cnt2=0;
priority_queue<int>node1;
priority_queue<int,vector<int>,greater<int> >node2;
int find1(int a) {
	if(a==fa1[a]) return a;
	else return fa1[a]=find1(fa1[a]);
}
int find2(int a) {
	if(a==fa2[a]) return a;
	else return fa2[a]=find2(fa2[a]);
}
int size1[maxn],size2[maxn];
void dfs(int x,int y) {
	for(int i=x-1;i<=x+1;i++) {
		for(int j=y-1;j<=y+1;j++) {
			if(i==x&&y==j) continue;
			if(i<1||j<1||i>4||j>m) continue;
			if(mp1[i][j]=='*') {
				if(find1((i-1)*m+j)==find1((x-1)*m+y)) continue;
				if(size1[find1((i-1)*m+j)]<=size1[find1((x-1)*m+y)]) {
					size1[find1((x-1)*m+y)]+=size1[find1((i-1)*m+j)];
					fa1[find1((i-1)*m+j)]=find1((x-1)*m+y);
				}else {
					size1[find1((i-1)*m+j)]+=size1[find1((x-1)*m+y)];
					fa1[find1((x-1)*m+y)]=find1((i-1)*m+j);	
					
				}
			}
		}
	}
}
void dfs2(int x,int y) {
	for(int i=x-1;i<=x+1;i++) {
		for(int j=y-1;j<=y+1;j++) {
			if(i==x&&y==j) continue;
			if(i<1||j>m||j<1||i>4) continue;
 			if(mp2[i][j]=='*') {
				if(find2((i-1)*m+j)==find2((x-1)*m+y)) continue;
				if(size2[find2((i-1)*m+j)]<=size2[find2((x-1)*m+y)]) {
					size2[find2((x-1)*m+y)]+=size2[find2((i-1)*m+j)];
					fa2[find2((i-1)*m+j)]=find2((x-1)*m+y);	
				}else {
					size2[find2((i-1)*m+j)]+=size2[find2((x-1)*m+y)];
					fa2[find2((x-1)*m+y)]=find2((i-1)*m+j);	
				}
			}
		}
	}
}
int main() {
	m=read();
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			fa1[(i-1)*m+j]=(i-1)*m+j;
			size1[(i-1)*m+j]=1;
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			cin>>mp1[i][j];
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			if(mp1[i][j]=='*') {
				dfs(i,j);
			}
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			if(fa1[(i-1)*m+j]==(i-1)*m+j&&mp1[i][j]=='*') {
				node1.push(size1[(i-1)*m+j]);
			}
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			fa2[(i-1)*m+j]=(i-1)*m+j;
			size2[(i-1)*m+j]=1;
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			cin>>mp2[i][j];
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			if(mp2[i][j]=='*') {
				dfs2(i,j);
			}
		}
	}
	for(int i=1;i<=4;i++) {
		for(int j=1;j<=m;j++) {
			if(fa2[(i-1)*m+j]==(i-1)*m+j&&mp2[i][j]=='*') {
				node2.push(size2[(i-1)*m+j]);
			}
		}
	}
	int ans=0;
	if(node2.size()<node1.size()) {
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=node1.size()-1;i++) {
		node2.pop();
	}
	while(node2.size()) {
		ans+=node2.top();
		node2.pop();
	}
	printf("%d\n",ans);
	return 0;
}