求助!! dfs 80分
查看原帖
求助!! dfs 80分
765418
anbo楼主2023/10/10 10:38
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010;
int vis[N];
int n,h,r;
int jud;
struct position
{
	ll x,y,z;
}p[N];
bool judge(position a,position b)
{
	ll d;
	d=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
	if(d<=4*r*r)	return true;
	else return false;
}
void dfs(int x)
{
	if(jud==1)	return ;
	if(p[x].z+r>=h)
	{
		jud=1;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==1) continue;
		else if(judge(p[x],p[i]))
		{
			vis[i]=1;
			dfs(i);
		}
	}
}
int main()
{
	//freopen("1902.in","r",stdin);
	//freopen("1902.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(p,0,sizeof p);
		jud=0;
		scanf("%d%d%d",&n,&h,&r);
		for(int i=1;i<=n;i++)	vis[i]=0;
		for(int i=1;i<=n;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			p[i]={x,y,z};
		}
		for(int i=1;i<=n;++i)
		{
			if(!vis[i]&&p[i].z<=r)
			{
				vis[i]=1;
				dfs(i);
			}
			if(jud==1)	break;
		}
		if(jud==1)	puts("Yes");
		else puts("No");
	}
	return 0;
}
2023/10/10 10:38
加载中...