原题链接：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
输入样例：
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
输出样例：
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; }
总结：
这类暴力搜索题一定要会，蓝桥杯每年都有这样暴力搜索题，后面还需要多加练习，文章写的急，若有错误请指出，大家一起加油。
