蜘蛛牌 HDU - 1584 （dfs，中間有些東西）

題目：

蜘蛛牌是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      

思路：就是暴力搜尋嘗試，找出最短移動距離，中間有個用距離的一個小減值，我做這道時，本來想，這當移動時，把移動的那張牌的位置變成目前移到這張牌的位置，本來想着是可以，但是若這張牌上有多張牌時，隻改變了直接移動的那一張牌的位置，下面其他牌的位置沒有改變，這樣再進行一下運算時，一定出錯。直接來一次标記，找下一個可以直接移動的牌，i~j中的牌，都在j牌上；直接用j牌的位置，當做i+1牌的位置就行，其實不是當做，現在的狀況，本來就是；

代碼：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define Max 15
#define INF 0x3f3f3f3f
int pos[Max];
int book[Max];
int ans;
int flag;
void dfs(int d,int step)
{
	if(step == 9)
	{
		ans = min(ans,d);
		flag = 1;
		return ;
	}
	for(int i = 1;i<=9;i++)
	{
		if(!book[i])    // 标記的意思是 還直接能不能用目前牌來移動。 
		{               // 沒有被标記，就是可以直接用目前牌來移動，也說明i+1牌一定可以放i這張牌 
			for(int j = i+1;j<=10;j++)
			{
				if(!book[j])   // 必須得标記，找下一可以直接移動的牌，i~j中的牌，都在j牌上； 
				{
					int tt = abs(pos[i] - pos[j]);
					if(d+tt>=ans) break;
					book[i] = 1;
					//int res = pos[i];     // 本來上面沒标記，就必須要把位置給改變了 
					//pos[i] = pos[j];     // 但是每一次移動都是職改變的剛移動的張牌的位置，
					dfs(d+tt,step + 1);     // 但那張牌下面的所有的位置都沒有改變，是以wrang anwer 
					book[i] = 0;
					//pos[i] = res;
					break;
				}
			
			}
		}
	}
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int k;
		ans = INF;
		memset(book,0,sizeof(book));
		for(int i = 0;i<10;i++)
		{
			scanf("%d",&k);
			pos[k] = i;
		}
		dfs(0,0);
		printf("%d\n",ans);
	}
	return 0; 
}