大家好,我是晴天学长,搜索型的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对象。文章来源:https://www.toymoban.com/news/detail-756820.html
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).总结
- 对于时间复杂度的判断。
试题链接:文章来源地址https://www.toymoban.com/news/detail-756820.html
到了这里,关于蓝桥杯算法心得——仙界诅咒(dfs)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!