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 ;
}