拯救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;
}

欢迎大家批评指正！！！