luogu 3958 奶酪

题目： 题目链接 注释：牛客数据水了 现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z = 0，奶酪的上表面为 z = h。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑 到奶酪的上表面去? 1、用并查集来解决 将上表面和下表面看做0和n+1，从1到n连接各个点， 如果洞和上表面相交或者相切，则连接，如果和下表面相切或者相交，那么连接，最后检查上表面和下表面是不是同一个祖先即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll n,h,r;
struct ty{
	ll x;
	ll y;
	ll z;
};
ty a[1005];
int pre[1005];
int find(int x){
	int r=x;
	while(r!=pre[r]){
		r=pre[r];
	}
	int j=x,temp;
	while(pre[j]!=r){
		temp=pre[j];
		pre[j]=r;
		j=temp;
	}
	return r;
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		pre[fx]=fy;
	}
	return ;
}
int visited[1005];
bool check(int i,int j){
	if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)<=4*r*r) return true;
	return false;
}
int main(){
	memset(visited,0,sizeof(visited));
	cin>>t;
	while(t--){
		cin>>n>>h>>r;
		for(int i=0;i<=n+1;i++) pre[i]=i;
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].z;
			if(a[i].z<=r) merge(0,i);
			if(a[i].z>=h-r) merge(n+1,i);
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(check(i,j)){
					merge(i,j);
				}
			}
		}
		if(find(0)==find(n+1)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

2、用dfs来解决 找到一个与下表面相交或者相切的点，然后开始从这个点开始遍历各个点，如果出现了与上表面相切或者相交的点，那么就输出Yes,否则输出No。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll n,h,r;
struct ty{
	ll x;
	ll y;
	ll z;
};
ty a[1005];
int visited[1005];
vector<int > g;
int flag=0;
bool check(int i,int j){
	if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)<=4*r*r) return true;
	return false;
}
void dfs(int x){
	if(flag==1) return ;
	if(a[x].z>=h-r){
		flag=1;
		return ;
	}
	visited[x]=1;
	for(int i=1;i<=n;i++){
		if(!visited[i]&&check(x,i)){
			dfs(i);
		}
	}
	return ;
}
int main(){
	cin>>t;
	while(t--){
		g.clear();//记得清除每一次的vector 
		flag=0;
		memset(visited,0,sizeof(visited));
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].z;
			if(a[i].z<=r) g.push_back(i);//将与小表面相邻的点存入vector中 
		}
		int len=g.size();
		for(int i=0;i<len;i++){
        //每一次dfs的visited数组没有更新为0，因为可以到达上层的路线不会和之前无法到达的路线连通，这样做反而对DFS进行了剪枝，使DFS的搜索次数减少
			if(flag==1) break;
			if(!visited[g[i]]){
				dfs(g[i]);
			}
		}  
		if(flag) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}