蓝桥杯倒计时47天！DFS基础——图的遍历
倒计时47天！
深度优先搜索——DFS
温馨提示：学习dfs之前最好先了解一下递归的思想。
DFS基础——图的遍历
仙境诅咒
问题描述
在一片神秘的仙境中，有N位修仙者，他们各自在仙境中独立修炼，拥有自己独特的修炼之道和修炼之地,修仙者们彼此之间相互尊重、和谐相处。
然而，有一天，仙境的主宰者妮妮(第一位修仙者)受到了诅咒，该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说，如果一个修仙者被诅咒，那么在距离他不超过D的范围内的所有修仙者都会被诅咒。
现在，你需要预测哪些修仙者最终会被诅咒，以便及时采取措施，保护仙境的和平与安宁。
输入格式
第一行输入一个正整数 N ( 1 < N ≤ 1 0 3 ) N(1<N≤10^3) N(1<N≤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 (1<=D<= 10^3) 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
题目分析
距离被诅咒者距离不超过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]==0&&dis(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[n+1];y = new double[n+1];v = new int[n+1];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]==0&&dis(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));
}
}