DFS深度优先搜索

数据范围不大,所以直接使用DFS深度优先搜索进行搜索即可。

首先输入数据,并定义一个数组来确定每个洞是否被访问过的状态。

随后对于与底面接触的洞进行访问,往四周进行DFS搜索,如果存在可以访问到的空洞与上表面相切或者相交说明搜索到了,输出Yes即可。

#include <bits/stdc++.h>
using namespace std;

typedef struct d {
	long long int x;
	long long int y;
	long long int z;
} d;//中心点
d k[1005];
int flag[1005];//空洞是否被访问过
long long int n, h;
double r;//距离
int fflag = 0;//输出的判断即是否搜索到了

double dis(long long int x1, long long int y1, long long int z1, long long int x2, long long int y2, long long int z2) {//距离
	return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2) + 1.0 * (z1 - z2) * (z1 - z2));
}

void dfs(long long int xx, long long int yy, long long int zz) {
	if (zz + r >= h) {//与顶部相切或相交
		fflag = 1;
		return ;
	}
	for (int i = 1; i <= n; i++) {
		if (!flag[i]) {//空洞未被访问过
			if (dis(xx, yy, zz, k[i].x, k[i].y, k[i].z) <= 2 * r) {//相切或相交
				flag[i] = 1;
				dfs(k[i].x, k[i].y, k[i].z);
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		memset(flag, 0, sizeof(flag));
		fflag = 0;
		cin >> n >> h >> r;
		for (int i = 1; i <= n; i++) {
			cin >> k[i].x >> k[i].y >> k[i].z;
		}
		for (int i = 1; i <= n; i++) {//1-n全部进行搜索
			if (!flag[i] && k[i].z <= r) {//未被访问过且与底部相交或相切
				flag[i] = 1;
				dfs(k[i].x, k[i].y, k[i].z);
			}
		}
		if (fflag)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
}

全部评论

相关推荐

想按时下班的大菠萝在...:隔壁学校的,加油多投, 实在不好找可以下个学期开学找,把算法八股准备好,项目有空再换换
投了多少份简历才上岸
点赞 评论 收藏
分享
07-15 14:14
门头沟学院 Java
7.10投递7.15感谢信
投递地平线等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务