求助,dfs30分,答案输出错误;
查看原帖
求助,dfs30分,答案输出错误;
295602
奈因楼主2020/10/25 17:19
#include <bits/stdc++.h>
using namespace std;
int a[10000000],b[10000000],c[10000000];
int t,l;
int n,h,r;
bool flag[10000000];
double ans(int x,int y)
{
return sqrt(pow(a[x]-a[y],2)+pow(b[x]-b[y],2)+pow(c[x]-c[y],2));
}
void dfs(int x)
{
if(c[x]+r>=h){
l=1;
return;
}
for(int i=x;i<=n;i++)    //老鼠进另外的空洞; 
         {			
if(abs(ans(x,i))<=2*r)
	{
if(!flag[i])
{
flag[i]=1;
dfs(i);
flag[i]=0;
}
	}
	    }
}
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n>>h>>r;
for(int j=1;j<=n;j++)
cin>>a[j]>>b[j]>>c[j];
for(int k=1;k<=n;k++)    //判断能否做出发点; 
{
if(c[k]==0)flag[k]=1;
else if(c[k]<0){
if(c[k]+r>=0)flag[k]=1;
}
else if(c[k]>0)
{
if(c[k]-r<=0)flag[k]=1;
}
}
for(int p=1;p<=n;p++)
if(flag[p])dfs(p);
if(l)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
l=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c)); 
memset(flag,0,sizeof(flag));
}
return 0;
}
2020/10/25 17:19
加载中...