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