题解 P3958 【奶酪】

· · 题解

感觉你们的代码都挺长的

一起来感受压行的乐趣吧

回到正题，看完这道题立马想到了搜索

但是对着数据范围疑惑了一下。

后来发现不用担心时间复杂度，这道题搜索特别快

关键是搜的方法要正确。首先要想去奶酪上面，先要有一个入口，也就是杰瑞的起点。如何确定起点呢？

很简单只要某个点高度减去半径小于等于0就好

确定了起点以后我们就可以开始搜了。

void search(int q){
    if(z[q]+r>=h) { pd=1; return ;}
    vis[q]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i] and dis(q,i)<=2*r) search(i);
    }
}

只要和这个洞挨着的洞，我们都要去一遍。而且实际上每个洞我们只需要去一遍。所以这里的vis数组记录了哪些洞去过 当我们发现到达顶部时就可以返回

那么如果到不了呢？

到不了还有其他没搜过的点啊

我们可以继续找找还有没有其他入口

如果真的都搜完了，那就只能输出No啦

最后一点，这道题有多次询问，所以别忘了初始化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int t,n,pd=0,vis[1005];
long long x[1005],y[1005],z[1005],h,r;
double dis(int a,int b){
    double x1=(double)x[a],y1=(double)y[a],z1=(double)z[a];
    double x2=(double)x[b],y2=(double)y[b],z2=(double)z[b];
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
void search(int q){
    if(z[q]+r>=h) { pd=1; return ;}
    vis[q]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i] and dis(q,i)<=2*r) search(i);
    }
}
int main(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        memset(x,-1,sizeof x); memset(y,-1,sizeof y);
        memset(z,-1,sizeof z); memset(vis,0,sizeof vis);
        scanf("%d%lld%lld",&n,&h,&r);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        }
        for(int i=1;i<=n;i++){
            if(!vis[i] and z[i]-r<=0) search(i);
            if(pd==1){ cout<<"Yes"<<endl; break;}
        }
        if(pd==0) cout<<"No"<<endl; pd=0;
    }
}