哈密顿绕行世界问题

简介: 一个规则的实心十二面体,它的 20个顶点标出世界著名的20个城市,你从一个城市出发经过每个城市刚好一次后回到出发的城市。

Input

前20行的第i行有3个数,表示与第i个城市相邻的3个城市.第20行以后每行有1个数m,m<=20,m>=1.m=0退出.

Output

输出从第m个城市出发经过每个城市1次又回到m的所有路线,如有多条路线,按字典序输出,每行1条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市.参看Sample output

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

Outout
1: 5 1 2 3 4 8 7 17 18 14 15 16 9 10 11 12 13 20 19 6 5
2: 5 1 2 3 4 8 9 10 11 12 13 20 19 18 14 15 16 17 7 6 5
3: 5 1 2 3 10 9 16 17 18 14 15 11 12 13 20 19 6 7 8 4 5
4: 5 1 2 3 10 11 12 13 20 19 6 7 17 18 14 15 16 9 8 4 5
5: 5 1 2 12 11 10 3 4 8 9 16 15 14 13 20 19 18 17 7 6 5
6: 5 1 2 12 11 15 14 13 20 19 18 17 16 9 10 3 4 8 7 6 5
7: 5 1 2 12 11 15 16 9 10 3 4 8 7 17 18 14 13 20 19 6 5
8: 5 1 2 12 11 15 16 17 18 14 13 20 19 6 7 8 9 10 3 4 5
9: 5 1 2 12 13 20 19 6 7 8 9 16 17 18 14 15 11 10 3 4 5
10: 5 1 2 12 13 20 19 18 14 15 11 10 3 4 8 9 16 17 7 6 5
11: 5 1 20 13 12 2 3 4 8 7 17 16 9 10 11 15 14 18 19 6 5
12: 5 1 20 13 12 2 3 10 11 15 14 18 19 6 7 17 16 9 8 4 5
13: 5 1 20 13 14 15 11 12 2 3 10 9 16 17 18 19 6 7 8 4 5
14: 5 1 20 13 14 15 16 9 10 11 12 2 3 4 8 7 17 18 19 6 5
15: 5 1 20 13 14 15 16 17 18 19 6 7 8 9 10 11 12 2 3 4 5
16: 5 1 20 13 14 18 19 6 7 17 16 15 11 12 2 3 10 9 8 4 5
17: 5 1 20 19 6 7 8 9 10 11 15 16 17 18 14 13 12 2 3 4 5
18: 5 1 20 19 6 7 17 18 14 13 12 2 3 10 11 15 16 9 8 4 5
19: 5 1 20 19 18 14 13 12 2 3 4 8 9 10 11 15 16 17 7 6 5
20: 5 1 20 19 18 17 16 9 10 11 15 14 13 12 2 3 4 8 7 6 5
21: 5 4 3 2 1 20 13 12 11 10 9 8 7 17 16 15 14 18 19 6 5
22: 5 4 3 2 1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
23: 5 4 3 2 12 11 10 9 8 7 6 19 18 17 16 15 14 13 20 1 5
24: 5 4 3 2 12 13 14 18 17 16 15 11 10 9 8 7 6 19 20 1 5
25: 5 4 3 10 9 8 7 6 19 20 13 14 18 17 16 15 11 12 2 1 5
26: 5 4 3 10 9 8 7 17 16 15 11 12 2 1 20 13 14 18 19 6 5
27: 5 4 3 10 11 12 2 1 20 13 14 15 16 9 8 7 17 18 19 6 5
28: 5 4 3 10 11 15 14 13 12 2 1 20 19 18 17 16 9 8 7 6 5
29: 5 4 3 10 11 15 14 18 17 16 9 8 7 6 19 20 13 12 2 1 5
30: 5 4 3 10 11 15 16 9 8 7 17 18 14 13 12 2 1 20 19 6 5
31: 5 4 8 7 6 19 18 17 16 9 10 3 2 12 11 15 14 13 20 1 5
32: 5 4 8 7 6 19 20 13 12 11 15 14 18 17 16 9 10 3 2 1 5
33: 5 4 8 7 17 16 9 10 3 2 1 20 13 12 11 15 14 18 19 6 5
34: 5 4 8 7 17 18 14 13 12 11 15 16 9 10 3 2 1 20 19 6 5
35: 5 4 8 9 10 3 2 1 20 19 18 14 13 12 11 15 16 17 7 6 5
36: 5 4 8 9 10 3 2 12 11 15 16 17 7 6 19 18 14 13 20 1 5
37: 5 4 8 9 16 15 11 10 3 2 12 13 14 18 17 7 6 19 20 1 5
38: 5 4 8 9 16 15 14 13 12 11 10 3 2 1 20 19 18 17 7 6 5
39: 5 4 8 9 16 15 14 18 17 7 6 19 20 13 12 11 10 3 2 1 5
40: 5 4 8 9 16 17 7 6 19 18 14 15 11 10 3 2 12 13 20 1 5
41: 5 6 7 8 4 3 2 12 13 14 15 11 10 9 16 17 18 19 20 1 5
42: 5 6 7 8 4 3 10 9 16 17 18 19 20 13 14 15 11 12 2 1 5
43: 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5
44: 5 6 7 8 9 16 17 18 19 20 1 2 12 13 14 15 11 10 3 4 5
45: 5 6 7 17 16 9 8 4 3 10 11 15 14 18 19 20 13 12 2 1 5
46: 5 6 7 17 16 15 11 10 9 8 4 3 2 12 13 14 18 19 20 1 5
47: 5 6 7 17 16 15 11 12 13 14 18 19 20 1 2 3 10 9 8 4 5
48: 5 6 7 17 16 15 14 18 19 20 13 12 11 10 9 8 4 3 2 1 5
49: 5 6 7 17 18 19 20 1 2 3 10 11 12 13 14 15 16 9 8 4 5
50: 5 6 7 17 18 19 20 13 14 15 16 9 8 4 3 10 11 12 2 1 5
51: 5 6 19 18 14 13 20 1 2 12 11 15 16 17 7 8 9 10 3 4 5
52: 5 6 19 18 14 15 11 10 9 16 17 7 8 4 3 2 12 13 20 1 5
53: 5 6 19 18 14 15 11 12 13 20 1 2 3 10 9 16 17 7 8 4 5
54: 5 6 19 18 14 15 16 17 7 8 9 10 11 12 13 20 1 2 3 4 5
55: 5 6 19 18 17 7 8 4 3 2 12 11 10 9 16 15 14 13 20 1 5
56: 5 6 19 18 17 7 8 9 16 15 14 13 20 1 2 12 11 10 3 4 5
57: 5 6 19 20 1 2 3 10 9 16 15 11 12 13 14 18 17 7 8 4 5
58: 5 6 19 20 1 2 12 13 14 18 17 7 8 9 16 15 11 10 3 4 5
59: 5 6 19 20 13 12 11 10 9 16 15 14 18 17 7 8 4 3 2 1 5
60: 5 6 19 20 13 14 18 17 7 8 4 3 10 9 16 15 11 12 2 1 5
思路:像这种类似排列的题,不用想就是dfs,用一个邻接表来存城市能到达的城市,数组来存城市路径。我写的时候调bug,发现我在最后面没有判断所到达的城市是否能回到原来的城市,卡了好久。哎!看题不仔细啊

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> Map[25];//邻接表存地图 
bool vis[25];
int m,cnt;
int ans[25];
void dfs(int cn)
{
    if(cn==20)//dfs的南墙 
    {
        int flag = 0;
        for(int i=0;i<3;i++)//判断是否可以回到起始城市 
        {
            if(Map[ans[cn]][i]==m)
            {
                flag = 1;
                break;
            }
        }
        if(flag)
        {
            cnt++;
            cout<<cnt<<":  ";
            for(int i=1;i<=20;i++)
            {
                cout<<ans[i]<<' ';
            }
            cout<<m<<endl;
        }
        return ;
    }
    int x = ans[cn];
    for(int i=0;i<Map[x].size();i++)
    {
        if(!vis[Map[x][i]])//判断是否已经走过 
        {
            ans[++cn] = Map[x][i];
            vis[Map[x][i]] = true;
            dfs(cn);
            vis[Map[x][i]] = false;//回溯 
            cn--;
        }
    }
}
int main()
{
    for(int i=1;i<=20;i++)//输入城市 
    {
        int x;
        for(int j=0;j<3;j++)
        {
            cin>>x;
            Map[i].push_back(x);
        }
    }
    while(cin>>m)
    {
        if(m==0) break;
        cnt = 0;
        memset(vis,false,sizeof(vis));//初始化 
        
        ans[1] = m;
        vis[m] = true;
        dfs(1);
    }
    return 0;
}
目录
相关文章
|
5月前
|
分布式计算 并行计算 Java
Python并发风暴来袭!IO密集型与CPU密集型任务并发策略大比拼,你站哪队?
【7月更文挑战第17天】Python并发处理IO密集型(如网络请求)与CPU密集型(如数学计算)任务。IO密集型适合多线程和异步IO,如`ThreadPoolExecutor`进行网页下载;CPU密集型推荐多进程,如`multiprocessing`模块进行并行计算。选择取决于任务类型,理解任务特性是关键,以实现最佳效率。
87 4
|
JavaScript 定位技术 数据格式
高德地图进阶开发实战案例(1):webAPI坐标转换和jsAPI批量转换
高德地图进阶开发实战案例(1):webAPI坐标转换和jsAPI批量转换
249 0
|
新零售 Linux 区块链
以太坊开发环境搭建linux版
本文介绍在ubuntu下如何搭建以太坊DApp的开发环境,包括nodejs、truffle、solc、web3js、ganache等。
2649 0
vba程序用7重循环来计算24
vba程序用7重循环来计算24
78 0
|
编解码 网络性能优化 网络架构
多媒体通信的服务质量 | 学习笔记
快速学习多媒体通信的服务质量,介绍了多媒体通信的服务质量系统机制, 以及在实际应用过程中如何使用。
多媒体通信的服务质量 | 学习笔记
|
Go 数据库
第三十八章 构建数据库应用程序 - 处理表单提交请求
第三十八章 构建数据库应用程序 - 处理表单提交请求
68 0
数字浙江的“时间减史”:引入阿里中台 让群众没有难办的事
9月25日,2019杭州云栖大会上,浙江政府首度集中公布了多项便民成果以及中台技术在数字浙江建设中的应用。
|
开发工具
R-Organize Data(step 2)
R is a data analysis and visualization platform.
939 0