HDU-1584-蜘蛛牌（DFS）

蜘蛛牌

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

Total Submission(s): 3561 Accepted Submission(s): 1529

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<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=;
const int INF=;
int num[maxn];//數字i的位置是num[i]
bool vis[maxn];//數字是否被通路過
int result;
void DFS(int steap,int deep)
{
    if(deep==)
    {
        result=min(result,steap);
        return;
    }
    for(int i=; i<=; i++) //枚舉數字
    {
        if(vis[i]==false)//如果此數字沒有出現過
        {
            vis[i]=true;//暫時标記已出現，防止接下來二次比對
            for(int j=i+;j<=;j++)
            {
                if(vis[j]==false)//遇到的第一個未标記過的數就是目标比對數
                {
                    DFS(steap+abs(num[i]-num[j]),deep+);
                    break;
                }
            }
            vis[i]=false;
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=; i<=; i++)
        {
            int x;
            scanf("%d",&x);
            num[x]=i;//數字x出現在第i位
        }
        result=INF;
        memset(vis,false,sizeof(vis));
        DFS(,);
        printf("%d\n",result);
    }
    return ;
}