大家好，我是晴天学长，搜索型的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）.总结
- 对于时间复杂度的判断。
试题链接：
文章出处登录后可见！
