HDU1584 蜘蛛牌（简单dfs）[C,C++]

Tama ·

更新时间:2024-11-10

· 573 次阅读

目录题目及翻译题面输入输出输入样例输出样例题目思路注意事项AC代码C/C++(几乎没有代码变更)Java 题目及翻译 题面

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

输出样例

题目思路

每张牌被合并后可以被认为"被使用过"，所以用vis把用过的牌记录下来
每次都找没用过的牌就行
数据范围很小，在10的范围内，dfs+简单剪枝即可
剪枝：
从一个数本身+1开始找下一个值，直到那个值没有被用过(也就是没有被合并到更大的纸牌上)
当计数大于已有答案时可以直接return

注意事项

计算距离要加abs

AC代码 C/C++(几乎没有代码变更)

用时124MS 内存1808K 长度658B

#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;//初始化的值
int n,ans;//样例个数和答案
int card[15],pos[15],vis[15];//分别记录每个位置的牌，每张牌的位置，和是否被使用过
void dfs(int cur,int cnt){//cur用于卡牌使用情况，默认为1张，cnt用来存当前计数距离
	if(cnt >= ans)return;//计数大于答案可以直接return，删去不影响AC但是很省时间
	if(cur == 10){//使用10张牌为搜索出口
		ans = min(ans,cnt);//更新答案
		return;
	}
	for(int i=0;i>n;//输入样例个数
	for(int i=0;i<n;++i){
		ans = INF;//初始化结果
		//vis不需要初始化，因为递归完vis已经回溯到初始状态了
		for(int i=0;i>card[i];//输入卡牌
			pos[card[i]] = i;//记录其位置
		}
		dfs(1,0);//dfs,从1开始，第10张牌不会被使用
		cout<<ans<<endl;//输出
	}
	return 0;
}

Java

待更新

本文作者 CSDN@扶她小藜
个人主页链接 https://blog.csdn.net/weixin_44579869

作者：扶她小藜

c+ dfs C++ hdu 蜘蛛

1024 个赞