蓝桥杯算法心得——仙界诅咒（dfs）

大家好，我是晴天学长，搜索型的dfs，差点开二维矩阵了，仔细一想，没那么夸张啊，哈哈哈，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

---

1) .仙界诅咒

仙境诅咒

问题描述

在一片神秘的仙境中，有N位修仙者，他们各自在仙境中独立修炼，拥有自己独特的修炼之道和修炼之地，修仙者们彼此之间相互尊重、和谐相处。

然而，有一天，仙境的主宰者妮妮（第一位修仙者）受到了诅咒，该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说，如果一个修仙者被诅咒，那么在距离他不超过D的范围内的所有修仙者都会被诅咒。

现在，你需要预测哪些修仙者最终会被诅咒，以便及时采取措施，保护仙境的和平与安宁。

输入格式

第—行输入一个正整数N(1 <N<.103)，表示仙境中有Ⅳ位修仙者。

接下来N行，每行两个实数X;和Y(-103<X;,Y <103 )，表示第à位修仙者的坐标(X;,Y)。第一位修仙者即仙境的主宰者妮妮。

最后一行输入一个正整数D(1<D<103），表示诅咒传播的范围。

输出格式

输出N行，每行一个整数，第i行的整数为1表示第i位修仙者最终被诅咒，为0则表示第i位修仙者没有被诅咒。
样例输入
5
0 0
1 1
0 1
1 0
2 2
1
样例输出
1
1
1
1
0

---

2) .算法思路

仙境诅咒

1.接收数据
2.循环数据，看与自己的直线距离是否满足D

---

3）.算法步骤

1.导入所需的Java I/O类和其他类。

2.声明静态变量和列表。

3.创建BufferedReader对象和PrintWriter对象，用于输入和输出。

4.读取输入的行，并解析为整数N（表示点的数量）。

5.创建布尔数组st，用于标记每个点是否被传播到。

6.使用循环读取每个点的坐标，并将其添加到xiuxian列表中。

7.读取输入的行，并解析为整数D（表示传播的最大距离）。

8.调用dfs方法开始传播，传入起始点的索引0、点的数量N、布尔数组st和最大传播距离D。

9.在dfs方法中，将当前点标记为已传播（st[i] = true）。

10.获取当前点的坐标s1。

11.遍历所有点的索引k。

12.检查点k是否未被传播（!st[k]）。

13.获取点k的坐标s2。

14.计算当前点到点k的距离distance，使用欧几里得距离公式。

15.如果距离小于等于最大传播距离D，递归调用dfs方法，传入点k的索引、点的数量N、布尔数组st和最大传播距离D。

16.在dfs方法结束后，返回上一层递归。

17.在主方法中，遍历所有点的索引i。

18.如果点i被传播到（st[i] = true），输出1；否则，输出0。

19.刷新输出流，并关闭PrintWriter对象。

---

4）. 代码实例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new PrintWriter(System.out));static String[] lines;static List<double[]> xiuxian = new ArrayList<>();public static void main(String[] args) throws IOException {lines = in.readLine().split(" ");int N = Integer.parseInt(lines[0]);boolean[] st = new boolean[N];for (int i = 0; i < N; i++) {lines = in.readLine().split(" ");double x = Double.parseDouble(lines[0]);double y = Double.parseDouble(lines[1]);xiuxian.add(new double[]{x, y});}lines = in.readLine().split(" ");int D = Integer.parseInt(lines[0]);// 开始传播dfs(0,N,st,D);for (int i = 0; i < N; i++) {if (st[i])out.println(1);else out.println(0);}out.flush();out.close();}private static void dfs(int i, int N, boolean[] st, int D) {st[i] = true;double[] s1 = xiuxian.get(i);for (int k = 0; k < N; k++) {if (!st[k]){double[] s2 = xiuxian.get(k);double distance = Math.sqrt((s2[0] - s1[0]) * (s2[0] - s1[0]) + (s2[1] - s1[1]) * (s2[1] - s1[1]));if (distance <= D) {dfs(k,N,st,D);}}}}
}

---

4）.总结

• 对于时间复杂度的判断。

---

试题链接：