hdu1584 蜘蛛牌 _DFS

蜘蛛牌

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

Total Submission(s): 3366    Accepted Submission(s): 1460

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

DFS+剪枝

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int INF = 100000000;

int card[12],vis[12],dist;

void dfs(int pos,int temp){  //pos：目前移動牌數；temp：目前移動距離 
	if(temp>=dist) return;  //剪枝，如果目前移動距離比最小全局移動距離還大，
	                        //則無需繼續進行搜尋該枝以下的情況 
	if(pos==9){  //牌面值為10的牌不移動，完成遊戲隻需移動9張牌 
		dist=temp;  //進入這個語句，說明目前值比原來的要優化
		return ;  //回溯 
	} 
	//如果還有未移動過的牌，則進行以下操作 
	for(int i=1;i<10;i++){  //'i'在這裡代表的是牌面值，循環終止條件為'i<10',
	                        //而非'i<=10',因為牌面值為10的牌不需要移動 
		if(!vis[i]){  //判斷牌面值為'i'是否通路過(是否移動過） 
			for(int j=i+1;j<=10;j++){  //若未通路過，則判斷牌i要移動到什麼位置 
				if(!vis[j]){  //比如要移動1，如果2,3,4,5都已經被移動過了
				               //那麼這幾張牌必定疊放在6的下面，是以要移到6的位置
					vis[i]=1;
					dfs(pos+1,temp+abs(card[i]-card[j]));
					break;  //不要在這個地方回溯，如果回溯了 
					       //比如2移到6了，結果回溯就直接跳過3~6到了7的下面
				}
			}
			vis[i]=0; //回溯時，恢複牌的通路狀态 
		}
	}
}

int main(){
	int t,a;
	cin>>t;
	while(t--){
		dist=INF;  //初始化最小距離盡可能大 
		for(int i=1;i<=10;i++){
			cin>>a;
			card[a]=i;  //牌面值為'a'的牌初始擺放的位置為'i' 
		}
		memset(vis,0,sizeof(vis));  //初始化所有牌的狀态為'未通路過'
		dfs(0,0);
		cout<<dist<<endl;
	}
	return 0;
}