首页 > 搜索 > DFS搜索 > HDU 1584 蜘蛛牌-DFS-[解题报告] C++
2013
12-12

HDU 1584 蜘蛛牌-DFS-[解题报告] C++

蜘蛛牌

问题描述 :

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

题目大意:本体是中文题,可以直接在OJ上看

/*
 * 1584_2.cpp
 *
 *  Created on: 2013年8月22日
 *      Author: Administrator
 */

#include <iostream>

using namespace std;

/**
 * vis[] :某一张牌的访问情况
 * a[s] = i ;牌面s在第i个位置
 * ans : 所需要的最小移动步数
 *
 */
const int maxn = 10000000;
int a[11];
bool visited[11];
int  ans;

/**
 * cur :当前移动牌数
 * temp :当前移动步数
 */
void dfs(int cur , int temp){
	//如果当前移动步数>=全局移动步数
	if(temp >= ans){
		return ;
	}
	//如果当前移动排数  == 9(为什么不==10呢??以为10是不需要移动的)
	if(cur == 9){
		ans = temp;
		return ;
	}

	int i,j;
	for( i = 1 ; i < 10 ; ++i){
		if(!visited[i]){
			for(j = i+1 ; j <= 10 ; ++j){ //这个用来确定i牌要移到什么位置
				if(!visited[j]){//比如要移1了,如果2,3,4,5都已经被移动过了 那么这几张牌必定叠放在6的下面,所以要移到6的位置
					visited[i] = true;
					dfs(cur + 1, temp + abs(a[i] - a[j]));
					break;//注意不要再这个地方回溯 如果回溯了 就像是又一个全排列 而且牌得移动不合理,比如2移到6了,结果回溯就直接跳过3~6到了7的下面
				}
			}
			visited[i] = false;
		}
	}
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--){

		memset(visited,false,sizeof(visited));
		ans = maxn;
		int i;
		for( i = 1 ; i <= 10 ; ++i){
			int s;
			scanf("%d",&s);
			a[s] = i;
		}

		dfs(0,0);
		printf("%d\n",ans);
	}
}

解题报告转自:http://blog.csdn.net/hjd_love_zzt/article/details/10189217


,
  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.