为什么dfs回溯会T后六个点,但把回溯去了就AC了?
正确的
#define ll long long
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
ll t,n,h,r;
ll x[100001],y[100001],z[100001];
ll book[1000001],flag;
unsigned ll js(ll i,ll k){
long long s;
s=(x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k])+(z[i]-z[k])*(z[i]-z[k]);
return s<=4*r*r;
}
void dfs(ll k){
if(z[k]+r>=h){
flag=1;
return ;
}
if(k>n)return ;
for(int i=1;i<=n;i++){
if(book[i]==0&&js(i,k)){
book[i]=1;
dfs(i);
}
}
//return ;
}
int main(){
cin>>t;
for(int i=1;i<=t;i++){
cin>>n>>h>>r;
for(int j=1;j<=n;j++){
cin>>x[j]>>y[j]>>z[j];
book[j]=0;
}
flag=0;
for(int j=1;j<=n;j++){
if(z[j]<=r)book[j]=1,dfs(j);
}
if(flag==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
T了的
#define ll long long
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
ll t,n,h,r;
ll x[100001],y[100001],z[100001];
ll book[1000001],flag;
unsigned ll js(ll i,ll k){
long long s;
s=(x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k])+(z[i]-z[k])*(z[i]-z[k]);
return s<=4*r*r;
}
void dfs(ll k){
if(z[k]+r>=h){
flag=1;
return ;
}
if(k>n)return ;
for(int i=1;i<=n;i++){
if(book[i]==0&&js(i,k)){
book[i]=1;
dfs(i);
book[i]=0;
}
}
//return ;
}
int main(){
cin>>t;
for(int i=1;i<=t;i++){
cin>>n>>h>>r;
for(int j=1;j<=n;j++){
cin>>x[j]>>y[j]>>z[j];
book[j]=0;
}
flag=0;
for(int j=1;j<=n;j++){
if(z[j]<=r)book[j]=1,dfs(j),book[j]=0;
}
if(flag==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}