第八周训练（C - Ice Skating ）

题意：有n个雪堆，一个人只能前后左右运动，求他需要添加几个雪堆才可以到达所有的雪堆

思路1（dfs）:可以从一个第一开始dfs(前提：改点没有经过)，判断是否可以到达所有的雪堆，每次dfs对答案+1，由于两个点才加一个雪堆，所以需要对与答案减1，或直接从-1开始

AC代码：

package 练习;
import java.util.*;
public class 练习 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x[]=new int [n+1];
int y[]=new int [n+1];
int arr[]=new int [n];
int ans=-1;
for(int i=0;i<n;i++){
x[i]=sc.nextInt();
y[i]=sc.nextInt();
}
for(int i=0;i<n;i++) {
if(arr[i]==0) {
dfs(x,y,arr,i);
ans++;
//System.out.println("ppppppp");
}
}
System.out.println(ans);
}
private static void dfs(int[] x, int[] y, int[] arr,int a) {
arr[a]=1;
for(int i=0;i<x.length;i++) {
if((x[a]==x[i]||y[a]==y[i])&&arr[i]==0) {
dfs(x,y,arr,i);
}
}
}
}

思路2（并查集）：感觉题解看的有点晕，等先你学习并差集再来补这种方法

最后

以上就是腼腆学姐最近收集整理的关于第八周训练（C - Ice Skating ）的全部内容，更多相关第八周训练（C内容请搜索靠谱客的其他文章。