大家好,我是晴天学长,搜索型的dfs,差点开二维矩阵了,仔细一想,没那么夸张啊,哈哈哈,需要的小伙伴可以关注支持一下哦!后续会继续更新的。
1) .仙界诅咒
仙境诅咒
问题描述
在一片神秘的仙境中,有N位修仙者,他们各自在仙境中独立修炼,拥有自己独特的修炼之道和修炼之地,修仙者们彼此之间相互尊重、和谐相处。
然而,有一天,仙境的主宰者妮妮(第一位修仙者)受到了诅咒,该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说,如果一个修仙者被诅咒,那么在距离他不超过D的范围内的所有修仙者都会被诅咒。
现在,你需要预测哪些修仙者最终会被诅咒,以便及时采取措施,保护仙境的和平与安宁。
输入格式
第—行输入一个正整数N(1 接下来N行,每行两个实数X;和Y(-103 最后一行输入一个正整数D(1 输出格式 输出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 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).总结 对于时间复杂度的判断。 试题链接: 参考文章
发表评论