HDU - 1584 蜘蛛牌 【DFS】
Description
蜘蛛牌是windows xp操作系统自带的一款纸牌游戏，游戏规则是这样的：只能将牌拖到比她大一的牌上面（A最小，K最大），如果拖动的牌上有按顺序排好的牌时，那么这些牌也跟着一起移动，游戏的目的是将所有的牌按同一花色从小到大排好，为了简单起见，我们的游戏只有同一花色的10张牌，从A到10，且随机的在一行上展开，编号从1到10，把第i号上的牌移到第j号牌上，移动距离为abs(i-j)，现在你要做的是求出完成游戏的最小移动距离。
Input第一个输入数据是T，表示数据的组数。
每组数据有一行，10个输入数据，数据的范围是[1,10]，分别表示A到10，我们保证每组数据都是合法的。
对应每组数据输出最小移动距离。
Sample Input
1
1 2 3 4 5 6 7 8 9 10
Sample Output
9
#include
#include
using namespace std;
int visit[20], a[20], min;
void dfs(int t, int sum) { //t代表已经移动了几张牌，sum代表目前移动耗费的步数
if(sum >= min)//超过最大步数的，即剪去
return;
if(t == 9) { //只用移动9次，10是固定不变的
min = sum;
return;
}
for(int i = 1; i < 10; i++) {
if(!visit[i]) {
visit[i] = 1;//标记用过了。
for(int j = i+1; j <= 10; j++) { //这个用来确定i牌要移到什么位置
if(!visit[j]) {
dfs(t+1, sum+abs(a[j]-a[i]));
break;
}
}
visit[i] = 0;//这里回溯
} // if
} // for
}
int main() {
int n, x;
scanf("%d", &n);
while(n--) {
for(int i = 0; i < 10; i++) {
scanf("%d", &x);
a[x] = i;//一：牌面为i的牌所在的位置
visit[i] = 0;
}
min = 1000000;//初始化一个最大值
dfs(0, 0);
printf("%d\n", min);
}
return 0;
}
作者：马小酥
