蒟蒻的玄学问题
查看原帖
蒟蒻的玄学问题
1221613
wangzc2012楼主2024/10/3 22:28

蒟蒻的玄学问题
请看 dfs 函数中的两个 for 循环(其中一个被注释了)。
如果使用第一个,只能得 1010 分,其余测试点 RERE ,但使用第二个,可以 ACAC 本题。
但是这两个 for 循环本质上似乎没有区别,想知道是哪里出问题了。

#include<bits/stdc++.h>
using namespace std;
int T,n,h,r,x[1005],y[1005],z[1005];
bool vis[1005],flag;
vector<int> t[1005];
double dist(double tx,double ty,double tz){
	return sqrt(tx*tx+ty*ty+tz*tz);
}
void dfs(int k){
	vis[k]=1;
	if (h-z[k]<=r){
		flag=1;
		return;
	}
	/*
	for (int i=0;i<=t[k].size()-1;i++){
		int v=t[k][i];
		if (vis[v]==0){
			dfs(v);
		}
	}
	*/
	for(int v : t[k]){
	    if(!vis[v]){
	    	dfs(v);
		}
	}
}
int main(){
    cin>>T;
    while (T--){
    	flag=0;
    	memset(vis,0,sizeof(vis));
    	for (int i=1;i<=n;i++) t[i].clear();
    	cin>>n>>h>>r;
		for (int i=1;i<=n;i++){
			cin>>x[i]>>y[i]>>z[i]; 
		} 
		for (int i=1;i<=n-1;i++){
			for (int j=i+1;j<=n;j++){
				if (dist((double)(x[i]-x[j]),double(y[i]-y[j]),double(z[i]-z[j]))<=(double)(r*2)){
					t[i].push_back(j);
					t[j].push_back(i);
				}
			}
		}
		for (int i=1;i<=n;i++){
			if (z[i]<=r){
				dfs(i);
				if (flag==1){
					cout<<"Yes"<<'\n';
					break;
				}
			}
		}
		if (flag==0) cout<<"No"<<'\n';
	}
    return 0;
}
2024/10/3 22:28
加载中...