hdu 2181(ハミルトンリング)
8668 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2181
ハミルトンリングを求め、可能なすべてのパスを出力させることです.
考え方:パスを1つの配列path[N]で保存し、暴捜すればよいが、戻るときはvisited[i]を0にすべきである.
View Code
ハミルトンリングを求め、可能なすべてのパスを出力させることです.
考え方:パスを1つの配列path[N]で保存し、暴捜すればよいが、戻るときはvisited[i]を0にすべきである.
View Code
1 #include<iostream>
2 const int N=20;
3 using namespace std;
4 int map[N+1][N+1];
5 int visited[N+1];
6 int path[N+1];
7 int m,_count=1;
8
9 void Initiate(){
10 int x;
11 memset(map,0,sizeof(map));
12 for(int i=1;i<=20;i++){
13 for(int j=1;j<=3;j++){
14 scanf("%d",&x);
15 map[i][x]=1;
16 }
17 }
18 }
19
20 void print(){
21 printf("%d: ",_count++);
22 for(int i=1;i<=20;i++){
23 printf("%d ",path[i]);
24 }
25 printf("%d
",m);
26 }
27
28
29
30 //now ，num
31 void dfs(int now,int num){
32 visited[now]=1;
33 path[num]=now;
34 if(num==N){
35 //
36 if(map[now][m]){
37 print();
38 }
39 }else {
40 for(int i=1;i<=N;i++){
41 if(!visited[i]&&map[now][i]){
42 dfs(i,num+1);
43 }
44 }
45 }
46 visited[now]=0;//
47 }
48
49
50
51 int main(){
52 Initiate();
53 while(~scanf("%d",&m)&&m){
54 memset(visited,0,sizeof(visited));
55 _count=1;
56 dfs(m,1);
57 }
58 return 1;
59 }