HDU 1584 （DFS好题）

蜘蛛牌 HDU - 1584

蜘蛛牌是windows xp操作系统自带的一款纸牌游戏，游戏规则是这样的：只能将牌拖到比她大一的牌上面（A最小，K最大），如果拖动的牌上有按顺序排好的牌时，那么这些牌也跟着一起移动，游戏的目的是将所有的牌按同一花色从小到大排好，为了简单起见，我们的游戏只有同一花色的10张牌，从A到10，且随机的在一行上展开，编号从1到10，把第i号上的牌移到第j号牌上，移动距离为abs(i-j)，现在你要做的是求出完成游戏的最小移动距离。

输入

第一个输入数据是T，表示数据的组数。
每组数据有一行，10个输入数据，数据的范围是[1,10]，分别表示A到10，我们保证每组数据都是合法的。

输出

对应每组数据输出最小移动距离。

输入

1
1 2 3 4 5 6 7 8 9 10

输出

9

思路

1.考虑到深度不是很深（10），如果用bfs则要用结构体存数组、且一层太宽、第一步（10个）第二步（10*10个）

2.首先随便尝试一个数 （位置为i、且i没移动过）找到比这个数大1的数（位置为J）
然后分两种情况：
① 位置为J的数字没有移动过：则把i 移动到J vis[i] = j
注意：位置 i 上可能有其他卡牌叠在上面 则要搜索 vis [k] == i （指向 i）的数把他们跟着 i 移动到 j 位置上

② 位置为 J 的数字移动了 （vis [ j ] 不等于0） 则把 i 移动到此时 J 所在位置上 vis[i] = vis[j] 同样把所有指向 i 的数 跟着移动

3.注意后面要还原状态 i 指向0 之前指向i 的数 还是值回 i

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int A[15];
int vis[15];
int ans;
const int INF = INT_MAX;
void dfs(int cur,int n) {
	if (cur == 9) {
		if (n < ans)ans = n;
		return;
	}
	else {
		int i, j, k;
		for (i = 1; i <= 10; i++) {
			for (j = 1; j <= 10; j++) {
				if (A[j] == A[i] + 1 && !vis[i] && A[i] != 10) {
					if (!vis[j]) {
						int idx = 0, tmp[10];
						n += abs(i - j);
						vis[i] = j;
						for (k = 1; k <= 10; k++) {
							if (vis[k] == i) {
								vis[k] = j;
								tmp[idx++] = k;
							}
						}
						dfs(cur + 1, n);
						vis[i] = 0;
						for (k = 0; k < idx; k++) {
							vis[tmp[k]] = i;
						}
						n -= abs(i - j);
					}
					else {
						int idx = 0 , tmp[10];
						n += abs(i - vis[j]);
						vis[i] = vis[j];
						for (k = 1; k <= 10; k++) {
							if (vis[k] == i)
							{
								vis[k] = vis[j];
								tmp[idx++] = k;
							}
						}
						dfs(cur + 1, n);
						vis[i] = 0;
						for (k = 0; k < idx; k++) {
							vis[tmp[k]] = i;
						}
						n -= abs(i - vis[j]);
					}
				}
			}
		}
	}
}
int main() {
	int T;
	while (scanf("%d", &T) != EOF && T) {
		while (T--) {
			int i; memset(A, 0, sizeof(A));
			memset(vis, 0, sizeof(vis));
			for (i = 1; i <= 10; i++) {
				scanf("%d", &A[i]);
			}
			ans = INF;
			dfs(0,0);
			printf("%d\n", ans);
		}
	}
	return 0;
}