做公司网站需不需要注册,计算机毕业设计代做网站,如何做网站淘宝客,新手如何自己做网站app倒计时47天#xff01;
深度优先搜索——DFS
温馨提示#xff1a;学习dfs之前最好先了解一下递归的思想。
DFS基础——图的遍历
仙境诅咒
问题描述
在一片神秘的仙境中#xff0c;有N位修仙者#xff0c;他们各自在仙境中独立修炼#xff0c;拥有自己独特的修炼之道…倒计时47天
深度优先搜索——DFS
温馨提示学习dfs之前最好先了解一下递归的思想。
DFS基础——图的遍历
仙境诅咒
问题描述
在一片神秘的仙境中有N位修仙者他们各自在仙境中独立修炼拥有自己独特的修炼之道和修炼之地,修仙者们彼此之间相互尊重、和谐相处。
然而有一天仙境的主宰者妮妮(第一位修仙者)受到了诅咒该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说如果一个修仙者被诅咒那么在距离他不超过D的范围内的所有修仙者都会被诅咒。
现在你需要预测哪些修仙者最终会被诅咒以便及时采取措施保护仙境的和平与安宁。
输入格式
第一行输入一个正整数 N ( 1 N ≤ 1 0 3 ) N(1N≤10^3) N(1N≤103)表示仙境中有N位修仙者。
接下来N行每行两个实数 X i X_i Xi和 Y i Y_i Yi$ (-103≤X_i,Y_i≤103) 表示第 i 位修仙者的坐标 表示第i位修仙者的坐标 表示第i位修仙者的坐标(X_i,Y_i)$。第一位修仙者即仙境的主宰者妮妮。
最后一行输入一个正整数 D ( 1 D 1 0 3 ) D (1D 10^3) 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题目分析
距离被诅咒者距离不超过D是其它修仙者都会被诅咒感染也就是我可以从当前被诅咒者走到距离不超过D的其它修仙者。我们可以用数组v[i]1表示修仙者i已经被诅咒。那么dfs过程代码如下
private static void dfs(int u) {v[u] 1;for(int i 1;i n;i)if(v[i]0dis(u,i)d)dfs(i);
}dfs(u)这里的u是已经被诅咒的修仙者那么v[u]就要被标记为1然后for循环遍历其它修仙者如果其它修仙者没有被诅咒并且与当前节点u的距离小于d那么说明当前修仙者会被传染成为新的被诅咒者这个时候就要进入dfs(i)去看i能传染给哪些人。
为什么要判断v[i]0防止重复遍历比如我从节点2进入了节点3即dfs(2)进入了dfs(3)在dfs(3)运行时我判断了dis(2,3)d如果我没有v[i]0的约束我会从dfs(3)进入dfs(2)再从dfs(2)进入dfs(3)最终产生了死循环。
dis函数就是已知两点坐标求两点距离的公式很简单但是注意这里有开根号那么会有小数在定义变量的时候要注意变量的类型。
private static double dis(int u, int v) {return Math.sqrt(Math.pow(x[u]-x[v], 2)Math.pow(y[u]-y[v], 2));
}最后通过数组v的值是否为1可以判断当前点是否被传染。
for(int i 1;i n;i) System.out.println(v[i]0?0:1);题目代码
import java.util.Scanner;
public class Main{static int n,d;static double x[],y[];static int v[];
public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();x new double[n1];y new double[n1];v new int[n1];for(int i 1;i n;i) {x[i] scanner.nextInt();y[i] scanner.nextInt();}d scanner.nextInt();dfs(1);for(int i 1;i n;i) System.out.println(v[i]0?0:1);
}
private static void dfs(int u) {// TODO Auto-generated method stubv[u] 1;for(int i 1;i n;i)if(v[i]0dis(u,i)d)dfs(i);
}
private static double dis(int u, int v) {// TODO Auto-generated method stubreturn Math.sqrt(Math.pow(x[u]-x[v], 2)Math.pow(y[u]-y[v], 2));
}
}
