hdu--1548--dfs--蜘蛛牌_shen_渊 的博客

/*
	Name: hdu--1548--蜘蛛牌
	Author: shen_渊 
	Date: 17/04/17 09:15
	Description: dfs,不好想，看两个大神的代码好久https://www.cnblogs.com/sook/archive/2011/03/27/1996775.html
											     https://blog.csdn.net/cscj2010/article/details/7364010 
*/
#include<iostream> 
#include<algorithm> 
#include<cstring>
using namespace std;
void dfs(int);
int vis[10],p[10];
int ans,ct;
int main(){
//	freopen("in.txt","r",stdin);
	ios::sync_with_stdio(false);
	int t;cin>>t;
	while(t--){
		memset(vis,0,sizeof(vis));
		memset(p,0,sizeof(p));
		ans = 0xffffff;//0在第一次递归排完之前不能停 
		ct = 0;
		for(int i=1; i<11; ++i){//p[a] 的位置为i 
			int a;cin>>a;
			p[a] = i;
		}
		dfs(1);
		cout<<ans<<endl;
	} 
	return 0;
}
void dfs(int num){//num是牌数 
	if(num == 10){
		ans = ct;
		return ;
	}
	for(int i=1; i<10; ++i){//i=1全排列不用等于10，毕竟有内循环 
		if(!vis[i]){
			for(int k=i+1; k<=10; ++k){// k<=10，p[10]是10的位置 可以等 
				if(!vis[k]){
					ct += abs(p[i]-p[k]);
					if(ans > ct){
						vis[i] = 1;
						dfs(num+1);
						vis[i] = 0;
					}
					ct -= abs(p[i]-p[k]);
					break;
				}
			}
		}
	}
}/*
	Name: hdu--1548--蜘蛛牌
	Author: shen_渊 
	Date