蜘蛛纸牌
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<iostream>
#include<string.h>
#include<cstdlib>
using namespace std;
int pos_card[15]; //用来存储某张牌的位置
int mark[15]; //用来做标记用的，
int min_sum; //用来记录最小的移动距离
void dfs(int k,int sum) //进行了k次对牌的移动操作，最当前小移动距离为sum
{
if(sum >= min_sum) //进行剪枝操作，如果当前最小移动距离sum 已经大于 之前 移动9张所用的最小移动的距离min_sum
return; //此时 这种深的情况 就没必要进行下去了
if(k == 9) //这里 k==9 时就可以 就有一种方案出现了，因为 已经把 移动了九张牌的位置放好了（10这张牌不可以被移动，所以只需要移动九张牌）
{
min_sum = sum;
}
for(int i=1;i<10;i++) //这里的 i 表示是牌上的数字（就是要被 移动的牌）
{
if(! mark[i]) //mark[i]=0 说明这张牌没有被移动过，那我们就可先选择 移动这张牌
{
mark[i] = 1; //设标记，表明该牌已经被移动过了，不能在被移到东了
for(int j=i+1;j<=10;j++) //这里的 j 表示 ，将i这张牌移动到 j 这张牌的上面（这里 有点难理解为什么是 “把i这张牌移到j牌上”，我们可能会想万一 j>i+1 ,这个时候 该次移动操作就不符合“把牌移到比她大1的牌上”的规则吗，）
{ //不必这样担心，因为如果 j>i+1,我们在这里假设 i = 2 ,j = 6 ；j为6说明 i=3,i=4,i=5 这三张牌已经被移动过了（因为此时的mark[3~5]=1，mark[6]=0），而且一定是这三张牌已经依照规则 先被移动到 6这张牌上面（这点一定要搞明白），
//此时 i这张牌要想有最小的位移 只能 被移到 6 这张牌的上面（因为在6这张牌的最上面为3这张牌）
if(! mark[j]) // mark[j] 为0 说明这张牌没有被移动过，知识又可能 有其他的牌移动到 这张牌的上面
{
dfs(k+1,sum+abs(pos_card[i] - pos_card[j]));
break; //这里的 break 也需要理解，这里的理解是 只要 i 这张牌 找到 一个 第一个放置位置，就不用再找放置位置了
}
}
mark[i] = 0; //回溯清除标记，进行下一种情况的尝试（这个需要自己理解）
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(mark,0,sizeof(mark));
min_sum = 1e9;
for(int i=1;i<=10;i++)
{
int temp;
cin>>temp;
pos_card[temp] = i; //pos_card[3] = 5; 3号牌的位置为5
}
dfs(0,0);
cout<<min_sum<<endl;
}
return 0;
}