题目链接:https://vjudge.net/contest/185350#problem/C
题目大意:一个规则的实心十二面体,它的 20个顶点标出世界著名的20个城市,你从一个城市出发经过每个城市刚好一次后回到出发的城市。输出从第m个城市出发经过每个城市1次又回到m的所有路线, 如有多个解,按字典序从小到大输出。
解题思路:题目很吓人,从起点DFS,重新回到起点是把路径输出来就行了,注意:下一个走的点要按从小到大的顺序,因为要使路径字典序从小到大。
代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 7 int point,cnt; 8 int map[25][25]; 9 int vis[25],path[25]; 10 11 void dfs(int pos,int len){ 12 vis[pos]=1; 13 //下个点按从小到大顺序走 14 for(int i=1;i<=20;i++){ 15 if(map[pos][i]){ 16 path[len]=pos; 17 if(i==point&&len==20){ 18 printf("%d: ",++cnt); 19 for(int i=1;i<=20;i++) 20 printf("%d ",path[i]); 21 printf("%d ",point); 22 } 23 if(!vis[i]) 24 dfs(i,len+1); 25 } 26 } 27 vis[pos]=0; 28 } 29 30 int main(){ 31 int a,b,c; 32 while(scanf("%d",&a)&&a){ 33 cnt=0; 34 memset(map,0,sizeof(map)); 35 scanf("%d%d",&b,&c); 36 map[1][a]=map[1][b]=map[1][c]=1; 37 for(int i=2;i<=20;i++){ 38 scanf("%d%d%d",&a,&b,&c); 39 map[i][a]=map[i][b]=map[i][c]=1; 40 } 41 scanf("%d",&point); 42 dfs(point,1); 43 } 44 return 0; 45 }