$O(n^2)$

主要是去判断上下是否连通，判断点是否连通，我们可以使用并查集进行维护。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010;
int p[N];
struct Sphere{
    LL x,y,z;
}q[N];
int find(int x)
{
    if(x!=p[x])
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        LL n,h,r;
        cin>>n>>h>>r;
        for(int i=0;i<=n+1;i++)
        {
            p[i]=i;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>q[i].x>>q[i].y>>q[i].z;
            if(q[i].z-r<=0&&q[i].z+r>=0)
            {
                p[find(0)]=i; //合并到0
            }
            if(q[i].z-r<=h&&q[i].z+r>=h)
            {
                p[find(n+1)]=i;//合并到n+1
            }
        }
        for(int i=1;i<=n;i++) //枚举两个点进行合并
        {
            for(int j=i+1;j<=n;j++)
            {
                LL dx=q[i].x-q[j].x,dy=q[i].y-q[j].y,dz=q[i].z-q[j].z;
                if(dx*dx+dy*dy+dz*dz<=4*r*r)
                {
                    p[find(i)]=find(j);
                }
            }
        }
        if(find(0)==find(n+1)) cout<<"Yes"<<endl; //起点和终点在一个集合之中
        else cout<<"No"<<endl;
    }
    return 0;
}

$n^2$

我们也可以使用bfs进行搜索，判断是否可以从下面走到上面。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
typedef long long LL;
struct Sphere{
    LL x,y,z;
}p[N];
bool st[N];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(st,0,sizeof st);//清空标记数组
        LL n,h,r;
        cin>>n>>h>>r;
        queue<int> q;
        for(int i=1;i<=n;i++)
        {
            int x,y,z;
            cin>>x>>y>>z;
            p[i]={x,y,z};
            if(z-r<=0&&z+r>=0)
            {
                q.push(i);   
                st[i]=1;//已经在队列之中
            }
        }
        int cnt=0;
        while(q.size())
        {
            if(cnt) break;
            int t=q.front();
            if(p[t].z+r>=h) //这个球跨越上下的面
            {
                cnt++;
                break;
            }
            q.pop();
            for(int i=1;i<=n;i++)
            {
                if(st[i]) continue;//当前点已经走过。
                LL dx=p[i].x-p[t].x,dy=p[i].y-p[t].y,dz=p[i].z-p[t].z;
                if(dx*dx+dy*dy+dz*dz<=4*r*r)
                {
                    q.push(i);
                    st[i]=1;//已经放入了队列之中
                    if(p[i].z+r>=h)
                    {
                        cnt++;
                        break;
                    }
                }
            }
        }
        if(cnt) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}