點擊打開鏈接

蜘蛛牌

Time Limit: 10000/5000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)

?

Total Submission(s): 5229????Accepted Submission(s): 2222

Problem Description

蜘蛛牌是windows xp操作系統自帶的一款紙牌游戲，游戲規則是這樣的：只能將牌拖到比她大一的牌上面（A最小，K最大），如果拖動的牌上有按順序排好的牌時，那么這些牌也跟著一起移動，游戲的目的是將所有的牌按同一花色從小到大排好，為了簡單起見，我們的游戲只有同一花色的10張牌，從A到10，且隨機的在一行上展開，編號從1到10，把第i號上的牌移到第j號牌上，移動距離為abs(i-j)，現在你要做的是求出完成游戲的最小移動距離。

Input

第一個輸入數據是T，表示數據的組數。
每組數據有一行，10個輸入數據，數據的范圍是[1,10]，分別表示A到10，我們保證每組數據都是合法的。

Output

對應每組數據輸出最小移動距離。

Sample Input

1

1 2 3 4 5 6 7 8 9 10

Sample Output

9

Author

xhd

Source

冬練三九之二

Recommend

lcy???|???We have carefully selected several similar problems for you:??1430?1732?1495?1518?1667

?思路：

搜索的策略是每次枚舉10張牌，看它可以放到哪張牌的上面

枚舉一下每次移動哪張牌，再判斷一下當前的這張牌要移動到哪張牌上

#include<bits/stdc++.h> using namespace std; int ans;//結果 int a[12];//每一個牌的位置 int mark[12];//表記是否移動過 void dfs(int num,int sum)//num是移動次數，sum是移動距離 {int i,j;if(sum>=ans) return ;//剪枝，ans是當前最優解if(num==9){ans=sum;return;}//搜索for(i=1;i<10;i++){if(!mark[i])//如果這張牌沒有移動過{mark[i]=1;//標記已經移動過//找到要移動到的地方//j就是移動的地方，因為移動到的地方肯定比i大for(j=i+1;j<=10;j++){if(!mark[j]){dfs(num+1,sum+abs(a[j]-a[i]));break;}}mark[i]=0;//回溯}} } int main() {int t,x;cin>>t;while(t--){for(int i=1;i<=10;i++){cin>>x;a[x]=i;}memset(mark,0,sizeof(mark));//把所有的牌都標記為沒有移動ans=10000;dfs(0,0);cout<<ans<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU1584 蜘蛛牌 DFS回溯的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。