题解：P3958 [NOIP2017 提高组] 奶酪
WoW_BBQ
·
·
题解
题意
问是否能通过空洞从下表面爬到上表面。
## 解题分析
这道题可以用 **dfs** 做，将空洞看为点，相切或相交则看作连边。
首先处理数据，看哪些空洞相切或相交，即两者球心距离小于半径 $r$，就将他们连边。
如果该空洞与下表面相切，就代表可以从该空洞开始搜索。
如果该空洞与上表面相切，就代表搜到该空洞即代表搜索通过，输出 `yes`。
所有路试完后仍未输出 `yes`，输出 `no`。
最后，**多测一定要清空**！
```cpp
#include<bits/stdc++.h>
using namespace std;
double t,n,h,r,f;
bool map1[1005][1005],visit[1005];
struct node{
double x,y,z;
}a[1005];
double dis(node a,node b){
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
}
void dfs(int p){
if(a[p].z+r>=h){f=1;return ;}
for(int i=1;i<=n;i++){
if(map1[p][i] and (!visit[i])){
visit[i]=1;
dfs(i);
}
}
return ;
}
queue<int> q;
int main(){
scanf("%lf",&t);
for(int i=1;i<=t;i++){
memset(map1,0,sizeof(map1));
memset(visit,0,sizeof(visit));
scanf("%lf%lf%lf",&n,&h,&r);
for(int j=1;j<=n;j++){
scanf("%lf%lf%lf",&a[j].x,&a[j].y,&a[j].z);
}
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(dis(a[j],a[k])<=r*2 and j!=k){
map1[j][k]=map1[k][j]=1;
}
}
if(a[j].z-r<=0){
q.push(j);
}
}
f=0;
while(!q.empty()){
visit[q.front()]=1;
dfs(q.front());
q.pop();
if(f){
printf("Yes\n");
while(!q.empty()){
q.pop();
}
}
memset(visit,0,sizeof(visit));
}
if(!f)printf("No\n");
}
return 0;
}
```