【NOIP2017提高组 A奶酪】题解

Jerry只是一只小老鼠，他不懂并查集，他只知道搜索......
我们假设Jerry有着超强的运动能力，它能够爬遍每个奶酪空洞，除非它已经到达了奶酪顶部。于是，我们可以先把所有的奶酪底部的空洞找出来，再从这些空洞开始广度优先搜索，直到搜到顶部的空洞为止。既然空间内两点距离可以求出，两个空洞是否相连就是两个空洞的中心点距离是否不大于空洞直径。脑力不行的Jerry已经等不及了，我们开始干吧！

#define MAXN 1001 // 最大空洞数量

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

class Cavity // 空洞类
{
public:
    long long x; // x坐标
    long long y; // y坐标
    long long z; // z坐标
};

int t;                       // 测试数据总数
int n;                       // 空洞数量
int h;                       // 奶酪高度
int r;                       // 空洞半径
int numLowerSurfaceCavities; // 下表面空洞数量

Cavity cavities[MAXN];             // 所有空洞
Cavity lowerSurfaceCavities[MAXN]; // 下表面的空洞
Cavity cavitiesHaveGone[MAXN];     // 经过的空洞

bool ifHaveGoneCavity[MAXN]; // 是否去过该空洞
bool ifCanGetTop;            // 能否到达顶部

double DistanceBetwinCavities (Cavity, Cavity);
void   GoFromCavity           (Cavity);
void   Init                   ();

int main(int argc, char const *argv[])
{
    scanf("%d", &t); // 输入t
    while (t--)      // 开始循环
    {
        Init();                        // 初始化
        scanf("%d %d %d", &n, &h, &r); // 输入n、h、r
        for (int i = 1; i <= n; i++)
        {
             // 输入各个空洞的坐标
            scanf("%lld %lld %lld", &cavities[i].x, &cavities[i].y, &cavities[i].z);
            if (cavities[i].z <= r) // 如果是下表面的空洞
            {
                 // 记录到 lowerSurfaceCavities 数组中
                lowerSurfaceCavities[++numLowerSurfaceCavities] = cavities[i];
            }
        }
        for (int i = 1; i <= numLowerSurfaceCavities; i++) // 枚举下表面的空洞
        {
            if (!ifCanGetTop) // 如果还不能到达顶部
            {
                 // 把经过的空洞的记录清空
                memset(ifHaveGoneCavity, false, sizeof(ifHaveGoneCavity));
                 // Jerry从这个空洞出发，开始BFS
                GoFromCavity(lowerSurfaceCavities[i]);
            }
            else // 已经证明可以到达顶部
            {
                break; // 直接退出
            }
        }
        if (ifCanGetTop) // 能到达顶部
        {
            printf("Yes\n"); // 输出 Yes
        }
        else // 不能到达
        {
            printf("No\n"); // 输出 No
        }
    }
    return 0;
}
 // 空洞之间的距离
double DistanceBetwinCavities(Cavity cavity1, Cavity cavity2)
{
    return sqrt(pow(cavity1.x - cavity2.x, 2) + pow(cavity1.y - cavity2.y, 2) + pow(cavity1.z - cavity2.z, 2));
}
 // 从空洞出发
void GoFromCavity(Cavity startCavity)
{
    int head = 0; // 队列头指针
    int tail = 1; // 队列尾指针

    cavitiesHaveGone[1] = startCavity; // 起点空洞先入队，Jerry走到起点

    do // Jerry开始往上爬
    {
        head++; // 头指针后移一位，指向要扩展的空洞（即下一步从该空洞出发）
        for (int i = 1; i <= n; i++) // 枚举所有的空洞
        {
             // 如果有空洞可以到达且该空洞没有到过（去过没到达顶部就不用去两回了）
            if (DistanceBetwinCavities(cavitiesHaveGone[head], cavities[i]) <= 2 * r && !ifHaveGoneCavity[i])
            {
                cavitiesHaveGone[++tail] = cavities[i]; // Jerry爬到该空洞
                ifHaveGoneCavity[i]      = true;        // 已经来过这个空洞了
                if (cavitiesHaveGone[tail].z + r >= h)  // 如果这个空洞是奶酪上表面的空洞（Jerry已经到了OvO）
                {
                    ifCanGetTop = true; // Jerry到达顶部了
                    return;             // 那还要继续爬吗？
                }
            }
        }
    } while (head < tail); // 一定要有恒心，只要没到达顶部，能爬多少就爬多少
}
 // 初始化
void Init()
{
    numLowerSurfaceCavities = 0;
    ifCanGetTop             = false;
}

Jerry认为我帮了他一个大忙，很感激我，为我点了个赞，那你呢？