做了一个拼图小游戏,需要找最少还原步骤(已确认排序可还原),网上说用康托算法重拍,但是没看明白,各位前辈有没有什么好的办法咯,或者解释一下康托算法也行咯!
1条回答 默认 最新
- 2022-01-23 13:30Jkchou2020的博客 康托展开（Cantor Expansion）是一个相对快速的判重方法，是一种特殊的哈希函数，其复杂度为O(n^2)，n是集合中元素的个数。函数康托Cantor()实现的功能是：输入一个排列，得到这个排列所对应的Cantor值。 2.举例 ...
- 2025-11-30 20:34宁柳跨越的博客 从里面我们能看到：抽象建模的重要性（康托编码）算法权衡的艺术（时间vs空间）工程思维的价值（防卡死、异常处理）科学验证的方法论（对照实验）下次当你看到类似问题时，不妨想想： 如何高效表示状态？ 能否设计更...
- 2024-08-02 16:00王禄DUT的博客 构建node数据结构储存每一种图的状态 利用route来记录路径。一道经典的八码图问题 使用bfs+康托哈希函数。memset(目标，原始，长度sizeof）memcmp(目标，原始，长度sizeof）memcpy(目标，原始，长度sizeof）
- 2022-11-14 10:00蓝色的烧烤的博客 } ④ 曼哈顿距离 A*算法的启发函数有多种设计方法，可以选择当前状态与目标状态位置不同的数字个数，也可以选择当前状态的逆序对数（目标状态逆序对数为0），还可以选择当前状态与目标状态的曼哈顿距离。...
- 2017-05-27 16:37哈哈哈哈666的博客 int get_hash(struct node e)//康托展开，压缩 { int a[9]; int i,j; int k=0; int ans=0; for(i=0;i;i++) { for(j=0;j;j++) { a[k++]=e.f[i][j]; } } for(i=0;i;i++) { k=0; for(j=0;j;j++) { if...
- 2017-07-10 00:55JackpotDC的博客 携程2017春招编程题——拼图题目解题思路基础的解决算法是BFS队列解决，但是会超时。所以需要去重。 去重要考虑格子重复的情况， 9个格子，所以拼图有9!种状态，建立visited[9!]布尔数组记录访问情况，如何判断两...
- 2018-04-27 20:57weixin_33827731的博客 偶尔看到网页上有缺一九宫格的小游戏，上手玩了几把，通过转圈法，把九宫格还原，虽然还原了，但是比较多的时间，带着疑问，于是就开始研究如何找到把缺一九宫格的最佳路径。 一，问题具体化 1）移动方式 ...
- 2015-03-17 12:57weixin_30732487的博客 Astar算法,就是一个给所有状态一个评估函数,优先选取较优状态向下搜的最好优先直接搜索算法,对于本题,我们设F(n)=g(n)+h(n)为估价函数,设g(n)为到达该状态已经走过的步数,h(n)为到最终答案的曼哈顿距离 因为该拼图...
- 2016-06-07 14:25octopusflying的博客 给出一个九宫格的拼图游戏的棋局，求完成拼图最少需要一定的步数。 解答： ·规则: 首先简要说明游戏规则。 游戏的棋局如下： 九宫格中放置8个标有不同数字的棋子，其中一个位置为空，通过...
- 2013-04-05 01:50weixin_30576859的博客 这里我们有一个可以定量化的衡量标准，也就是说，我们可以以该状态还原为目标状态（这里称为Goal-Status）所需的最小步数为一个凭据。当然，这样比较单纯，我们还可以设计出更“客观”一些的，比如，有些移动是难以...
- 2013-04-05 17:12weixin_30821731的博客 一个描述局面信息的数据结构 64 65 struct node 66 67 { 68 69 // 利用vector容器装填当前的状态 70 71 vector < int > state; 72 73 // 装填一个最优解，...
- 2025-10-11 08:57带你玩遍北海道的博客 八数码问题是在一个 $3 \times 3$ 的棋盘上进行的滑动拼图游戏，其中八个编号为1~8的方块和一个空格（用0表示）可沿上下左右方向移动。所有合法状态构成的状态空间共包含 $9!= 362,880$ 种排列，但仅有一半（即 $9!/...
- 2013-02-08 17:06fengsser的博客 前段时间在玩仙五前，遇上了蚩尤冢拼图这个小游戏。 其实就是八数码问题，一直想着如何才能用最少步数求解，于是就写了个程序。 Q1：什么是八数码问题？ A1：首先假定一个3*3的棋盘（如上图），分别有1，2，3……8 ...
- 2015-06-05 18:56speedboy007的博客 这里我们有一个可以定量化的衡量标准，也就是说，我们可以以该状态还原为目标状态（这里称为Goal-Status）所需的最小步数为一个凭据。当然，这样比较单纯，我们还可以设计出更“客观”一些的，比如，有些移动是难以...
- 2021-06-20 03:25" sicily1151魔板"问题的解决可能还需要结合其他数据结构和算法，如哈希表（用于存储已访问状态，防止重复搜索）或剪枝策略（减少不必要的搜索）。此外，理解和优化代码的时间复杂度与空间复杂度也至关重要，以确保...
- 2024-03-21 06:30躺柒的博客 在由数据驱动的市场环境中，算法对我们的行为数据（如生活喜好、认知偏见、保留价格）进行收集与处理，并将这些信息应用到了日后的交易过程中 5.2. 价格是由消费者需求与市场供给共同决定 5.2.1. 需求量越高，...
- 2019-07-19 22:17我会魔法丶的博客 Sample Input 2 3 4 1 5 x 7 6 8 Sample Output ullddrurdllurdruldr 题目链接 https://vjudge.net/problem/HDU-1043 其实就是反向bfs，不过用了一个新的方法去存放拼图序列，康托展开即把拼图(x12345678)全排列，...
- 2025-10-03 23:28潮水岩的博客 本章将从整体视角出发，介绍ACM竞赛中高频出现的核心算法类别，包括排序、搜索、图论、动态规划、贪心策略、数据结构、数论与字符串处理等，并阐述“模板化编程”在高压限时比赛中的战略意义——通过预研与固化经典...
- 2025-10-20 00:21ArcCl的博客 条件是否必需数组有序✅ 是支持随机访问✅ 是（不能用于普通链表）元素可比较✅ 是存在唯一解❌ 否（可处理多个解）...综上所述，快速排序、归并排序与二分查找不仅是独立的算法模块，更是构成高级解题技巧的基础构件。
- 没有解决我的问题, 去提问
