WA了,但是案例能过555
查看原帖
WA了,但是案例能过555
662697
A765422804楼主2022/1/16 16:32

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;
}
2022/1/16 16:32
加载中...