dfs做法补充
一定记得要把所有数组初始化啊!!!
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 10, M = N * N;
int h[N], e[M], ne[M], idx;
typedef long long LL;
struct node
{
int x, y, z;
}q[N];
bool st[N];
int t, n, hh, r;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int now)
{
st[now] = true;
if (now == 1) return true;
for (int i = h[now]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j] && dfs(j)) return true;
}
return false;
}
int main()
{
cin >> t;
while (t --)
{
memset(h, -1, sizeof h);
memset(e, 0, sizeof e);
memset(ne, 0, sizeof ne);
memset(st, false, sizeof st);
idx = 0;
cin >> n >> hh >> r;
for (int i = 2; i <= n + 1; i ++)
{
int x, y, z;
cin >> x >> y >> z;
q[i] = {x, y, z};
if (abs(z) <= r) add(0, i), add(i, 0);
if (abs(hh - z) <= r) add(1, i), add(i, 1);
}
for (int i = 2; i < n + 1; i ++)
for (int j = i + 1; j <= n + 1; j ++)
{
LL dx = q[i].x - q[j].x;
LL dy = q[i].y - q[j].y;
LL dz = q[i].z - q[j].z;
if (dx * dx + dy * dy + dz * dz <= 4 * (LL)r * r)
add(i, j), add(j, i);
}
if (dfs(0)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}