拯救007[天体赛 -- 深度优先遍历]

本文主要是介绍拯救007[天体赛 -- 深度优先遍历]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入样例1
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
输出样例1
Yes输入样例2
4 13
-12 12
12 12
-12 -12
12 -12
输出样例2
No

思路

bfs

题目大意：从池心岛中心(0, 0)跳出鳄鱼池

存储结构
1.用一个结构体数组存放鳄鱼的坐标及其距离池心岛的距离
2.用vis数组存储每一只鳄鱼被踩过的情况

bfs具体流程
1.首先将可以从池心岛中心(0,0)一步到达的鳄鱼入队
2.不断取出队首元素，判断从当前点是否可以跳到边界，如果可以，结束bfs；否则，遍历所有鳄鱼，找到没有被踩过，且可以从当前点过去的，将其入队
3.直到队列为空

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef struct 
{double x, y; //鳄鱼的坐标double distance; //鳄鱼距离池心岛中心边界的距离
}crocodile;
crocodile c[N];
bool vis[N]; //标记每个鳄鱼是否被踩过
int n, d;
double cal_dist(int x, int y)
{return sqrt(x * x + y * y) - 7.5;
}
bool Judge(int x, int y)
{if(x + d >= 50 || x - d <= -50) //从左右边界出去return true;if(y + d >= 50 || y - d <= -50) //从上下边界出去return true;return false;
}
bool bfs()
{queue<crocodile> q;for(int i = 0; i < n; i ++) //第一次可以踩到的鳄鱼{if(d >= c[i].distance){vis[i] = true;q.push(c[i]);}}while(!q.empty()){crocodile temp = q.front();q.pop();if(Judge(temp.x, temp.y)) return true;for(int i = 0; i < n; i ++) //寻找下一个可以到达的鳄鱼{//没有被踩过，且可以一步到达if(!vis[i] && temp.distance + d >= c[i].distance){vis[i] = true;q.push(c[i]);}}}return false;
}
int main()
{cin >> n >> d;for(int i = 0; i < n; i ++){cin >> c[i].x >> c[i].y;c[i].distance = cal_dist(c[i].x, c[i].y);}if(bfs()) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

欢迎大家批评指正！！！

这篇关于拯救007[天体赛 -- 深度优先遍历]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---