深搜,亮点在那个剪枝,flag代表是否搜索数组从开始到当前一直等于原始数组同位置的数,如果是真,就从原始数组的当前位置的书开始搜,否则就从0开始搜。

见代码。

#include <iostream>
#include <cstring> using namespace std;
int n,m,beg,origin[2003];
int mp[103][103];
bool vis[103][103];
int cnt;
int stk[2010];
bool check()
{
int i;
for(i=0;i<=m;i++)
{
if(stk[i]==origin[i])
continue;
if(stk[i]<origin[i])
return false;
if(stk[i]>origin[i])
return true;
}
return false;
} void dfs(int bg,bool flag)
{
// cout<<cnt<<endl;
if(cnt==m+1)
{
// for(int i=0;i<=m;i++)
// cout<<stk[i]<<' ';
// cout<<endl;
if(stk[cnt-1]==beg&&check())
{
return;
}
else
{
return;
}
}
for(int i=1;i<=n;i++)
{
if(flag&&i<origin[cnt])
continue;
if(mp[bg][i]&&!vis[bg][i])
{
vis[bg][i]=true;
vis[i][bg]=true;
stk[cnt++]=i;
dfs(i,flag&&i==origin[cnt-1]);
// cout<<stk[cnt]<<endl;
if(cnt==m+1&&stk[cnt-1]==beg&&check())
return;
// cout<<" "<<cnt<<endl;
cnt--;
// cout<<" "<<cnt<<endl;
vis[bg][i]=false;
vis[i][bg]=false;
}
}
return;
}
int main()
{
cin>>n>>m;
int i;
cnt=1;
memset(mp,0,sizeof(mp));
memset(vis,false,sizeof(vis));
cin>>origin[0];
beg=origin[0];
for(i=1;i<=m;i++)
{
cin>>origin[i];
mp[origin[i-1]][origin[i]]=1;
mp[origin[i]][origin[i-1]]=1;
}
//// for(i=1;i<=n;i++)
////// {
////// for(int j=1;j<=n;j++)
////// cout<<mp[i][j]<<' ';
////// cout<<endl;
//// }
stk[0]=beg;
dfs(beg,true);
// cout<<cnt<<endl;
if(cnt==m+1)
{
for(i=0;i<=m;i++)
cout<<stk[i]<<' ';
cout<<endl;
}
else
cout<<"No solution"<<endl;
return 0;
}

  

最新文章

  1. JavaScript深入浅出6-函数和作用域
  2. JQM---列车时刻查询
  3. Swift语言实战晋级-第9章 游戏实战-跑酷熊猫-4 熊猫的跳和打滚
  4. uva 11520 - Fill the Square
  5. HDU 3436--Queue-jumpers (树状数组 or Splay Tree)
  6. 编译Firebird的源码
  7. tbb 线程安全concurrent_queue的性能
  8. React文档(十八)最佳性能
  9. RK3288 uboot启动流程
  10. ORACLE数据恢复方法(提交事务也可以)
  11. 【特性】MySQL 8 新特性
  12. 日期时间函数 mysql 和sqlserver 中对于常用函数的日期和时间函数的区别
  13. [UE4]自定义函数,快速增加输入参数的一种方法
  14. title
  15. springmvc使用包装的pojo接收商品信息的查询条件
  16. 理解 RESTful 架构(转)
  17. [ruby]rubyGem出现ERROR: Could not find a valid gem时的处理方法
  18. Python装饰器高级用法
  19. js小数乘法精确率问题
  20. MB/s与Mbit/s的区别

热门文章

  1. sqlserver 导出数据库表结构和数据生成脚本
  2. python 循环设计
  3. java代码抓取网页邮箱
  4. query attr prop区别
  5. Help Me Escape (ZOJ 3640)
  6. 第七章 企业项目开发--本地缓存guava cache
  7. PL/SQL设置编码方式
  8. JVM调优(这里主要是针对优化基于分布式Mahout的推荐引擎)
  9. 如何对ConnectionString进行加密解码?
  10. VS2003编译后的网站如何修改代码