救救孩子吧给我整自闭了啊啊啊啊啊 80分 DFS做法 最后两个测试点WA
查看原帖
救救孩子吧给我整自闭了啊啊啊啊啊 80分 DFS做法 最后两个测试点WA
414220
2019lzh楼主2022/10/21 19:50
#include<bits/stdc++.h>
using namespace std;
int t,n,h,r,x,y,z;
struct center{
	long long x,y,z;
	bool Used;
}p[1001]; 
bool ans=0;
long long dist(center p1,center p2)
{
	return ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}//输出距离 
void dfs(int m){ 
	if(ans==1) return;
	if(h-p[m].z<=r) 
	{
		ans=1; 
		return;
	}
	///////////////完成任务 
	p[m].Used=1;
	for(int i=1;i<=n;i++) 
	{
		//if(i==m) i++;
		if(dist(p[m],p[i])<=(4*r*r)&&p[i].Used==0) 
		{
			dfs(i);//深度优先搜索
			//p[i].Used=0;
		}	
	}
	/////////////还需继续搜索 
}//DFS
int main()
{
	//freopen("iin.in","r",stdin);
	//freopen("oout.out","w",stdout);
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>n>>h>>r;
		for(int j=1;j<=n;j++)
		{
			cin>>p[j].x >>p[j].y >>p[j].z;//输入点坐标 
			p[j].Used =0; 
		}
		for(int i=1;i<=n;i++)
		{
			if(p[i].z<=r) dfs(i);
			//else cout<<"No"<<return 0;
		}//寻找是否有点满足最底层并DFS 
		if(ans==1) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		ans=0;
	}
	return 0;
} 

贴心地附上相似的AC代码(题解的)

#include<bits/stdc++.h>
using namespace std;
int n,v[1005],t,ok;
double x[1005],y[1005],z[1005],h,r;
bool e(int i,int j){
    double dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
    return dis<=4*r*r;
}
void dfs(int k){
    if(ok)return;
    if(z[k]+r>=h){
        ok=1;
        return;
    }
    v[k]=1;
    for(int i=1;i<=n;i++)
    if(!v[i]&&e(i,k))
    dfs(i);
}
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
    	memset(v,0,sizeof(v));//记得清零
        ok=0;
        cin>>n>>h>>r;
        for(int j=1;j<=n;j++)
        cin>>x[j]>>y[j]>>z[j];
        for(int j=1;j<=n;j++)
        if(z[j]-r<=0)
        dfs(j);
        if(ok)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
} 

贴心地附上错误数据之一

2 5100500 1275250
0 0 1275250
0 50500 3825250
2022/10/21 19:50
加载中...