首页 > 其他 > 详细

HDU 1584(蜘蛛牌 DFS)

时间:2018-09-21 22:01:46      阅读:36      评论:0      收藏:0      [点我收藏+]

标签:name   print   .html   题意   break   src   using   .cn   set   

题意是在蜘蛛纸牌的背景下求 10 个数的最小移动距离。

在数组中存储 10 个数字各自的位置,用深搜回溯的方法求解。

代码如下:

技术分享图片
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int ans,a[20];
 4 bool vis[20];
 5 void dfs(int num,int sum)
 6 {
 7     if(sum > ans) return;
 8     if(num == 9)
 9     {
10         ans = sum;
11         return;
12     }
13     for(int i = 1; i <= 10; ++i)
14     {
15         if(!vis[i])
16         {
17             vis[i] = 1;
18             for(int j = i+1; j <= 10; ++j)
19             {
20                 if(!vis[j])
21                 {
22                     dfs(num+1,sum+abs(a[i]-a[j]));
23                     break;
24                 }
25             }
26             vis[i] = 0;
27         }
28     }
29 }
30 int main()
31 {
32     int t,tmp;
33     scanf("%d",&t);
34     while(t--)
35     {
36         for(int i = 1; i <= 10; ++i)
37         {
38             scanf("%d",&tmp);
39             a[tmp] = i;
40         }
41         memset(vis,0,sizeof(vis));
42         ans = 1000000;
43         dfs(0,0);
44         printf("%d\n",ans);
45     }
46     return 0;
47 }
View Code

向这些博客的作者表示感谢:

https://blog.csdn.net/flynn_curry/article/details/50775604

https://www.cnblogs.com/yanqi110/articles/4928285.html

HDU 1584(蜘蛛牌 DFS)

标签:name   print   .html   题意   break   src   using   .cn   set   

原文:https://www.cnblogs.com/Taskr212/p/9614126.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号