原题链接：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
输入样例：
代码语言：javascript复制3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4输出样例：
代码语言：javascript复制Yes
No
YesDFS（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代码：
代码语言：javascript复制#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
代码语言：javascript复制#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;
}总结：
这类暴力搜索题一定要会，蓝桥杯每年都有这样暴力搜索题，后面还需要多加练习，文章写的急，若有错误请指出，大家一起加油。
