HDU——1584 蜘蛛牌（剪枝 + dfs）

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

代碼：

#include <cstdio>
#include <string.h>
using namespace std;

int index[] ;  // index[x] = y 表示牌面為 x 的紙牌 ，存放的位置是 y；
int visited[];
int ans;
int change(int a , int b){
    int c = a - b;
    if(c <= )
        return -c;
    return c;
}
void dfs(int num , int sum){  //num表示目前已将排好序的紙牌的張數 ， sum代表到目前為止移動步數之和
    int i , j;
    if(sum > ans)    //剪枝（優化），沒有可能會逾時。
        return;
    if( num == ) {//已經排好序
        if(sum < ans)
            ans = sum;
        return;
    }
    for(i =  ; i <=  ; i ++){
        if(visited[i] == ){
            visited[i] = ;
            for(j = i +  ; j <=  ; j ++ ){   //尋找可以與這一堆 相接的下一堆。
                 if(visited[j] == ){
                    dfs(num +  , sum + change(index[i] , index[j]));
                    break;   //找到可以移動的目标牌 ， 這次尋找就結束。
                    //不要接着找下一個沒有移動過的位置，隻有查找到的第一個未被移動的位置才是符合條件（>1)的位置。
                }
            }
            visited[i] = ;   //回溯 ， 如果沒有找到可以移動的牌，此時就要還原現場，便于下一次查找
        }
    }
}
int main(){
    int T , i;
    scanf("%d" , &T);
    while( T --){
        memset(index ,  , sizeof(index));
        memset(visited ,  , sizeof(visited));

        for( i =  ; i <=  ; i ++){
            int temp;
            scanf("%d",&temp);
            index[temp] = i;
        }
        ans = ;   //儲存已經周遊過的移動方案中 步數最少的那一次的步數。
        dfs( , );

        printf("%d\n",ans);
    }
    return ;
}