AcWing 528. 奶酪（每日一题）

题目：

DFS（BFS）：

并查集：

总结：

原题链接：528. 奶酪 - AcWing题库

题目：

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。

我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z=0，奶酪的上表面为 z=h。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。

如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?

空间内两点 P1(x1,y1,z1)、P2(x2,y2,z2) 的距离公式如下：

输入格式

每个输入文件包含多组数据。

输入文件的第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。

接下来是 T 组数据，每组数据的格式如下：

第一行包含三个正整数 n，h，和 r，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。

接下来的 n 行，每行包含三个整数 x、y、z，两个数之间以一个空格分开，表示空洞球心坐标为 (x,y,z)。

输出格式

输出文件包含 T 行，分别对应 T 组数据的答案，如果在第 i 组数据中，Jerry 能从下表面跑到上表面，则输出 Yes，如果不能，则输出 No。

数据范围

1≤n≤1000,
1≤h,r≤10^9,
T≤20,
坐标的绝对值不超过10^9

输入样例：

输出样例：

Yes
No
Yes

DFS（BFS）：

看到这样的题直接考虑爆搜，去dfs每一个点看看是否满足条件，最后高度是否能到达h，在dfs上优化一下，我们可以sort排序一下每个点的高度，这样我遍历上可以一路走到头，比如我此时高度high=4，奶酪高度h=8，那么排序完之后，a[i].z<4的点我不用再去考虑了，在i+1基础上去遍历，使其优化一点。

相交或者相切条件： (x1-x2)^2+(y1-y2)^2+(z1-z2)^2<=(2*r)^2

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,r,h;
int T;
bool flag;//判断是否能到达h
const int N=1005;
struct node{//结构体存储
	ll x,y,z;
}a[N];
bool vis[N];//标记数组
bool cmp(node A,node B){//排序函数
	return A.z<B.z;
}
void dfs(int dep,int hig){//dep表示搜索第i个，hig为当前高度
	if(hig>=h){//大于h说明到达了，不需要再搜了
		flag=1;
		return;
	}
	vis[dep]=1;//不管能不能走先标记
	for(int i=dep+1;i<=n;i++){
		int x1=abs(a[i].x-a[dep].x);
		int y1=abs(a[i].y-a[dep].y);
		int z1=abs(a[i].z-a[dep].z);
		if(!vis[i]&&(ll)x1*x1+(ll)y1*y1+(ll)z1*z1<=(ll)4*r*r){//满足相交或相切条件
            dfs(i,a[i].z+r);//从i个开始搜，当前高度不要忘记加r
        }
	}
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>a[i].x>>a[i].y>>a[i].z;
		}
		flag=0;//多组输入注意初始化
		memset(vis,0,sizeof(vis));
		sort(a+1,a+n+1,cmp);
		for(int i=1;i<=n;i++){
			if(!vis[i]&&a[i].z<=r){//只要此点可以满足入口条件就可以进入搜，可以有多个入口
				dfs(i,a[i].z+r);
			}
			if(flag==1){//只要找到一种方案能到达h，任务就完成了
				break;
			}
		}
		if(flag==0){
			cout<<"No"<<endl;
		}else{
			cout<<"Yes"<<endl;
		}
	}
	return 0;
}

并查集：

y总讲解并查集解法：AcWing 528. 奶酪（每日一题）_哔哩哔哩_bilibili

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010;
struct point{
    int x,y,z;
}pt[N];
int p[N];
int up[N],down[N];

double distance(point p1,point p2){
    return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2)+pow(p1.z-p2.z,2));
}

int find(int x){
    if(p[x] != x){
        p[x] = find(p[x]);
    }
    return p[x];
}

int main(){
    int t;
    cin>>t;

    while(t--){
        int n,h,r;
        int t1 = 0,t2 = 0;
        cin>>n>>h>>r;

        for(int i = 1;i<=n;i++) p[i] = i;

        for(int i=1;i<=n;i++){
            cin>>pt[i].x>>pt[i].y>>pt[i].z;
            if(pt[i].z-r<=0) down[++t1] = i;//记录联通上下表面的点
            if(pt[i].z+r>=h) up[++t2] = i;
        }

        if(t1 == 0||t2 == 0) {
            cout<<"No"<<endl;
            continue;
        }

        //遍历所有的点处理连通集
        for(int i = 1;i<=n;i++)
           for(int j = i+1;j<=n;j++){
               if(find(i) == find(j)) continue;
               double dis = distance(pt[i],pt[j]);
               if(dis<=2*r) p[find(i)] = find(j);//合并
           }
        int flag = 0;
        //检查连通集
        for(int i = 1;i<=t1;i++){
            if(flag) break;
            for(int j = 1;j<=t2;j++){
                if(find(down[i]) == find(up[j]) ) {
                    cout<<"Yes"<<endl;
                    flag = 1;
                    break;
            }
        }
     }
     if(flag == 0) cout<<"No"<<endl;
   }
   return 0;

}