【蓝桥杯】0仙境诅咒 — BFS/DFS 图论连通性问题（C++ 题解）

【蓝桥杯】0仙境诅咒 — BFS/DFS 图论连通性问题（C++ 题解）

1. 题目描述

• 题目来源：蓝桥云课 - 0仙境诅咒
• 难度：易 (LV.1)
• 标签：DFS / BFS / 图的连通性

问题简述

在仙境中有 N 位修仙者，坐标分别为 (X_i, Y_i)。第一位修仙者（妮妮，即下标为 0 的修仙者）受到了诅咒。
诅咒具有传递性：如果一个修仙者被诅咒，那么距离他不超过 D 的范围内的所有修仙者也都会被诅咒。
请求出最终哪些修仙者会被诅咒。

• 数据范围：
  • 1 <= N <= 1000
  • -1000 <= X_i, Y_i <= 1000（坐标为实数）
  • 1 <= D <= 1000

---

2. 常见误区与原代码分析

很多初学者容易将题目理解为“只计算每个人到原点 (0,0) 或妮妮的距离”。

典型错误思路：

• 仅判断每个修仙者到妮妮的距离是否 <= D。
• 忽略了连通性（连锁传播）：即便修仙者 C 距离妮妮超过 D，但只要 C 距离“已被诅咒的修仙者 B”不超过 D，C 就会被感染。

---

3. 解题思路

本题本质上是一个无向图的连通块遍历问题：

1. 建立连通关系：两点 u 和 v 之间的欧氏距离小于等于 D（即 (X_u - X_v)^2 + (Y_u - Y_v)^2 <= D^2）时，两点之间存在一条无向边。
2. 图的遍历：从起点 0（妮妮）开始，使用 BFS（广度优先搜索） 或 DFS（深度优先搜索） 遍历所有可达的点。
3. 精度处理：坐标为实数，计算距离平方时用 double 存储，比较时可加上微小的浮点误差容限（如 1e-9）。

由于 N <= 1000，整体判断的复杂度为 O(N^2)，可以完美在 2 秒内通过。

---

4. C++ AC 代码

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

// 计算两点之间的欧氏距离平方
double distSq(double x1, double y1, double x2, double y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<pair<double, double>> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
    }

    double d;
    cin >> d;
    double d2 = d * d; // 距离阈值的平方

    vector<bool> vis(n, false);
    queue<int> q;

    // 起点：第 0 位修仙者（妮妮）首先被诅咒
    vis[0] = true;
    q.push(0);

    // BFS 遍历
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v = 0; v < n; v++) {
            if (!vis[v]) {
                // 判断 u 与 v 之间的距离平方是否 <= D^2
                if (distSq(p[u].first, p[u].second, p[v].first, p[v].second) <= d2 + 1e-9) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }

    // 顺序输出结果
    for (int i = 0; i < n; i++) {
        cout << (vis[i] ? 1 : 0) << "\n";
    }
    return 0;
}

5. 复杂度分析

• 时间复杂度：$\mathcal{O}(N^2)$
  每个节点入队一次，遍历每个节点时扫描其余 $N$ 个节点，对 $N\le 1000$ 而言，计算量约为 $10^6$ 次，轻松在 2 秒限制内跑完。

• 空间复杂度：$\mathcal{O}(N)$
  仅需存储 $N$ 个点的坐标数组、访问标记数组 vis 及 BFS 队列。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/aqiu111111/article/details/166741100