第八周训练（C - Ice Skating ）

118 阅读 0 评论 78 点赞

我是靠谱客的博主腼腆学姐，这篇文章主要介绍第八周训练（C - Ice Skating ），现在分享给大家，希望可以做个参考。

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

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

AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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);
}
}
}
}