一个规则的实心十二面体，它的 20个顶点标出世界著名的20个城市，你从一个城市出发经过每个城市刚好一次后回到出发的城市。 Input 前20行的第i行有3个数,表示与第i个城市相邻的3个城市.第20行以后每行有1个数m,m<=20,m>=1.m=0退出. Output 输出从第m个城市出发经过每个城市1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市.参看Sample output
搜索，深度优先
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <queue> #include <cmath> using namespace std; int x[21][3]={0},num,ans[21]={0},lu[21]={0},keyy; int f(int n,int key) { if(n==20&&ans[keyy]==0) { printf("%d: ",num++); int i; for(i=0;i<20;i++) printf("%d ",lu[i]); printf("%d",keyy); printf("\n"); return 0; } ans[key]=1;lu[n]=key; if(ans[x[key][0]]==0) f(n+1,x[key][0]); if(ans[x[key][1]]==0) f(n+1,x[key][1]); if(ans[x[key][2]]==0) f(n+1,x[key][2]); ans[key]=0;lu[n]=0; return 0; } int main() { int i,j,key; for(i=1;i<=20;i++) { scanf("%d",&x[i][0]); scanf("%d",&x[i][1]); scanf("%d",&x[i][2]); } while(1) { num=1; ans[0]=0;ans[1]=0;ans[2]=0;ans[3]=0;ans[4]=0; ans[5]=0;ans[6]=0;ans[7]=0;ans[8]=0;ans[9]=0; ans[10]=0;ans[11]=0;ans[12]=0;ans[13]=0;ans[14]=0; ans[15]=0;ans[16]=0;ans[17]=0;ans[18]=0;ans[19]=0;ans[20]=0; scanf("%d",&key); if(key==0) break; lu[0]=key; keyy=key; f(1,x[key][0]); f(1,x[key][1]); f(1,x[key][2]); } return 0; }搜索 用数组存储走过的路，走过的标记并不再走，若步数达到20布即已经走遍所有，打印。 第一个与最后一个题目已经给出。
