zoj 3761（并查集+搜索）
时间：2014-03-05 17:44:52
收藏：0
阅读：563
题意：在一个平面上，有若干个球，给出球的坐标，每次可以将一个球朝另一个球打过去（只有上下左右），碰到下一个球之后原先的球停下来，然后被撞的球朝这个方向移动，直到有一个球再也撞不到下一个球后，这个球飞出，球只能是朝上下左右四个方向打，并且要一个球四个方向都没有球了，这个球就不能打了。问说最少平面上剩几个球，并且给出打球的方案。
思路：把四个方向可以连成一块的球用一个并查集连起来，有多少个并查集，最后就会剩下多少个球，然后就是从并查集的叶子节点往根结点输出路径。这里要注意，不能重复输出，还有就是，在击打球的时候，有一个先后顺序，我们输出的时候，必须严格按照这个顺序，就是说，每次必须先把父节点所有的枝路径全部输出后，才能输出这个父节点及其父节点的路径........
|
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120 |
#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>using
namespace std;int father[2005],rank[2005],n,num[2005];int s[2005][2];bool
vist[2005],vist1[2005],vist2[2005];void
dfs(int
v){ if(num[v]>=2) { num[v]--; return; } if(father[v]==v) return; if(!vist2[v]) { if(rank[v]==0) printf("(%d, %d) LEFT\n",s[v][0],s[v][1]); if(rank[v]==1) printf("(%d, %d) RIGHT\n",s[v][0],s[v][1]); if(rank[v]==2) printf("(%d, %d) DOWN\n",s[v][0],s[v][1]); if(rank[v]==3) printf("(%d, %d) UP\n",s[v][0],s[v][1]); } vist2[v]=true; dfs(father[v]);}void
dfs1(int
i){ for(int
j=0; j<n; j++) { if(vist[j]) continue; /*if(s[i][0]==s[j][0]&&s[i][1]==s[j][1]) { father[j]=i; rank[j]=1; vist[j]=true; vist1[i]=true; dfs1(j); }*/ if(s[i][0]==s[j][0]&&s[i][1]<s[j][1]) { father[j]=i; rank[j]=2; num[i]++; vist[j]=true; vist1[i]=true; dfs1(j); } if(s[i][0]==s[j][0]&&s[i][1]>s[j][1]) { father[j]=i; rank[j]=3; num[i]++; vist[j]=true; vist1[i]=true; dfs1(j); } if(s[i][1]==s[j][1]&&s[i][0]<s[j][0]) { father[j]=i; rank[j]=0; num[i]++; vist[j]=true; vist1[i]=true; dfs1(j); } if(s[i][1]==s[j][1]&&s[i][0]>s[j][0]) { father[j]=i; rank[j]=1; num[i]++; vist[j]=true; vist1[i]=true; dfs1(j); } }}int
main(){ while(scanf("%d",&n)>0) { for(int
i=0; i<=n; i++) { father[i]=i; rank[i]=-1; num[i]=0; } memset(vist,false,sizeof(vist)); memset(vist1,false,sizeof(vist1)); memset(vist2,false,sizeof(vist2)); for(int
i=0; i<n; i++) { scanf("%d%d",&s[i][0],&s[i][1]); } for(int
i=0; i<n; i++) { if(vist[i]) continue; vist[i]=true; dfs1(i); } int
cnt=0; for(int
i=0; i<n; i++) { if(father[i]==i) cnt++; } printf("%d\n",cnt); for(int
i=0; i<n; i++) if(!vist1[i]) { dfs(i); } } return
0;} |
zoj 3761（并查集+搜索）,布布扣,bubuko.com
原文：http://www.cnblogs.com/ziyi--caolu/p/3581365.html
评论（0）