思路:
先看哪两个点能互通,再广搜寻找下一步,如果到达高度h就输出Yes,如果所有路径都找过都不能到达高度h就输出No。
#include<bits/stdc++.h>
using namespace std;
long long t;
long long n,h,r;
long long x[],y[],z[];
long long maap[][];
long long book[];
long long flag=;
long long p;//用long long(数据范围大)
int juli(long long a,long long b,long long c,long long d,long long e,long long f)
{
double sum1=sqrt((a-b)*(a-b)+(c-d)*(c-d)+(e-f)*(e-f));//判断两个点之间的距离
double bj=*r;//double既不会爆有可以对付小数问题
if(sum1<=bj) return ;//如果两个圆心的距离小于等于两个半径,说明这两个洞连着
else return ;
}
int main()
{
cin>>t;
queue<int> q;//初始化队列
while(t--)//t组数据
{
flag=;//判断有没有输出
while(!q.empty())q.pop();
memset(book,,sizeof(book));
memset(maap,,sizeof(maap));//初始化
//maap储存地图maap[i][j]储存i和j能不能相连
cin>>n>>h>>r;//输入
for(long long i=;i<=n;i++)
{
cin>>x[i]>>y[i]>>z[i];//输入
if(z[i]+r>=h)book[i]=;//判断第i个能不能到顶层,如果能book[i]=2
if(z[i]-r<=)q.push(i);//如果这个点能到地面,就把它推入队列,准备广搜
}
for(long long i=;i<=n;i++)
for(long long j=i;j<=n;j++)
if(juli(x[i],x[j],y[i],y[j],z[i],z[j])==)
{
maap[i][j]=;
maap[j][i]=;
}//判断i和j能否相连,储存在maap里
while(!q.empty())
{
p=q.front();//取一个点开始广搜
q.pop();//搜过的点pop
if(book[p]==)
{
cout<<"Yes"<<endl;
flag=;
break;
}//如果这个点p可以到顶层,就输出yes,flag=1(代表已经输出过)
if(book[p]!=)
{
book[p]=;//一个点不能重复走(实际可以,但是没有意义
for(long long k=;k<=n;k++)
if(maap[p][k]==)//如果现在的点p可以到点k
q.push(k);//把k推入队列,广搜
}
}
if(flag==)//如果flag=0,说明没有输出过,也就是说不能到达顶层,输出-1;
cout<<"No"<<endl;
}
return ;
}
请各位大佬斧正