【蓝桥杯】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. 解题思路

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

由于 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 队列。