bfs写的,不知道哪里出了问题,感谢大佬
#include <iostream>
#include<queue>
#include <cmath>
using namespace std;
int space_x[1000];
int space_y[1000];
int space_z[1000];
int map[1000];
bool bfs(int n,int h,int r)
{
queue<int>qx;
queue<int>qy;
queue<int>qz;
for (int i = 0; i < n; i++)
{
if (space_x[i] == 0 && space_y[i] == 0 && space_z[i] > 0 && space_z[i] <= r)
{
qx.push(space_x[i]);
qy.push(space_y[i]);
qz.push(space_z[i]);
map[i] = 1;
}
}
while (!qx.empty())
{
int now_x = qx.front();
int now_y = qy.front();
int now_z = qz.front();
qx.pop();
qy.pop();
qz.pop();
if (h - now_z <= r)
{
return true;
}
else
{
for (int i = 0; i < n; i++)
{
if (map[i] == 0 && sqrt(pow(now_x - space_x[i], 2) + pow(now_y - space_y[i], 2) + pow(now_z - space_z[i], 2)) <= 2*r)
{
map[i] = 1;
qx.push(space_x[i]);
qy.push(space_y[i]);
qz.push(space_z[i]);
}
}
}
}
return false;
}
int main()
{
int T;//数据个数
cin >> T;
int n, h, r;//空洞数量、奶酪高度和空洞半径
for (int i = 0; i < T; i++)
{
cin >> n >> h >> r;
for (int i = 0; i < n; i++)
{
cin >> space_x[i];
cin >> space_y[i];
cin >> space_z[i];
}
if (bfs(n,h,r) == true)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
for (int i = 0; i < n; i++)
{
map[i] = 0;
space_x[i] = 0;
space_y[i] = 0;
space_z[i] = 0;
}
}
return 0;
}