BFS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1010;
int t, n, h, r;
struct node
{
int x, y, z;
} p[N];
int q[N];
bool st[N];
bool check(node &a, node &b)
{
LL dis = (1ll * a.x - b.x) * (1ll * a.x - b.x) + (1ll * a.y - b.y) * (1ll * a.y - b.y) + (1ll * a.z - b.z) * (1ll * a.z - b.z);
LL radius = 1ll * r * r;
return dis <= 4 * radius;
}
bool bfs()
{
int hh = 0, tt = -1;
for (int i = 0; i < n; i++) if (p[i].z <= r)
q[++tt] = i,
st[i] = true;
while (hh <= tt)
{
auto index = q[hh++];
if (p[index].z + r >= h)
return true;
for (int i = 0; i < n; i++)
{
if (st[i])
continue;
if (check(p[index], p[i]))
{
st[i] = true;
q[++tt] = i;
if (p[i].z + r >= h)
return true;
}
}
}
return false;
}
int main()
{
cin >> t;
while (t--)
{
cin >> n >> h >> r;
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y >> p[i].z;
memset(st, 0, sizeof st);
if (bfs())
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
并查集
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1010;
struct node{
int x, y, z;
}f[N];
int p[N];
int t, n, h, r;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool check(node &a, node &b)
{
LL dis = (1ll * a.x - b.x) * (1ll * a.x - b.x) + (1ll * a.y - b.y) * (1ll * a.y - b.y) + (1ll * a.z - b.z) * (1ll * a.z - b.z);
LL radius = 1ll * r * r;
return dis <= 4 * radius;
}
int main()
{
cin >> t;
while(t --){
cin >> n >> h >> r;
for(int i = 0; i < n; i ++){
cin >> f[i].x >> f[i].y >> f[i].z;
p[i] = i;
}
for(int i = 0; i < n; i ++)
for(int j = i + 1; j < n; j ++){
if(check(f[i], f[j])) p[find(i)] = find(j);
}
bool flag = false;
for(int i = 0; i < n; i ++){
if(f[i].z <= r){
for(int j = 0; j < n; j ++){
if(f[j].z + r >= h && flag != true){
if(find(i) == find(j)){
cout << "Yes" << endl;
flag = true;
break;
}
}
}
}
}
if(!flag) cout << "No" << endl;
}
return 0;
}