Introduction
牛牛子想当嘉然小姐的狗，但嘉然小姐喜欢的是猫，于是他在纸上画了一个规则的实心十二面体，这个十二面体上面的 20个顶点标出的20个国家，牛牛子想从一个国家出发经过每个国家恰好一次后回到出发的国家。但是他不懂，你能帮帮他吗？
Input
前20行的第i行有3个数,表示与第i个国家相邻的3个国家.第20行以后每行有1个数m,m<=20,m>=1.m=0退出.
Output
输出牛牛子从第m个国家出发经过每个国家1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的国家.参看Sample outpu
Sample
input
2 5 20 1 3 12 2 4 10 3 5 8 1 4 6 5 7 19 6 8 17 4 7 9 8 10 16 3 9 11 10 12 15 2 11 13 12 14 20 13 15 18 11 14 16 9 15 17 7 16 18 14 17 19 6 18 20 1 13 19 5 0
Solution
import java.util.Scanner; public class Main5 { static int[][] graph=new int[21][21]; static int[] vis=new int[21]; static int[] ans=new int[22]; static int k; static int num=1; public static void main(String[] args) { Scanner s=new Scanner(System.in); for (int i=1;i<=20;i++){ for (int j=1;j<=3;j++){ graph[i][j]=s.nextInt(); } } while (true){ k=s.nextInt(); if (k==0)break; num=1; dfs(k,1); } } static void dfs(int x,int step){ if(step==21&&x==k){ System.out.print(num+": "); for(int i=1;i<=20;i++){ System.out.print(" "+ans[i]); } System.out.print(" "+x); System.out.println(); num++; return; } if(vis[x]==1){ return; } vis[x]=1; ans[step]=x; for (int i=1;i<=3;i++){ int next=graph[x][i]; dfs(next,step+1); } vis[x]=0; ans[step]=0; } }
Experience
首先要想到是dfs
