一个奇怪的问题
查看原帖
一个奇怪的问题
169736
Fu_Tao楼主2021/7/26 09:30

为什么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;
}
2021/7/26 09:30
加载中...