Problem 1073 --搜索-八数码BFS

1073: 搜索-八数码BFS

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 12  Solved: 7
[Submit][Status][Web Board][Creator:]

Description

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

Input

输入初试状态,一行九个数字,空格用0表示

Output

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

Sample Input

283104765

Sample Output

4

HINT


康拓展开



如果按照平常的思路,把x的位置看做0,一共有8!个状态,来判断某一个状态是否被访问过。 

但是问题来了?怎么把一个带有x的数组转变为转变为数字呢?第一个联想到的就是STL中的map,但是map的速度太慢了,会超时,这个时候我们就要用一种快速的方法把这个带有x的数组转换为数组,那就是hash,如何hash就是用康拓展开这个公式。 

这个公式的描述:X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!ai表示所有未出现的元素中比ai这个元素小的个数,他是最小的就为0. 

这个里面有几个关键词就是前面未出现的所有元素和为出现的元素; 

我们来举个例子 

数组 {1,2,3} 按从小到大的排列一共6个:123 132 213 231 312 321。 

有一个数组{2,5,7,8}求它的一个排列7528的对应的值 

a4=’7’(注意这里的7表示的是元素,不是数字,下同) 这个元素在 前面未出现的所有元素{2,5,7,8}中是前面有几个比它小数?其中2,5都比他小所以a4 = 2; 

a3=’5’这个元素在前面未出现的所有元素{2,5,7}(元素’8’已经出现过了,所以不满足红字的条件)中,有一个比它小的数字,所以a3 = 1; 

a3=’2’这个元素在前面未出现的所有元素{2,7}中,有0个比它小的数字,所以a3 = 0; 

a3=’8’这个元素在前面未出现的所有元素{7}中,有0个比它小的数字,所以a3 = 1; 

所以X = a4*(4-1)!+a3*(3-1)!+a2*(2-1)!+a1*(1-1)!; 

X = 2*(3!) + 1*(2!) +0*(1!) + 0*(0!); 

= 14 

上面就是康拓展开的一般过程,简单描述为已知一个排列,就能知道这个排列中元素的个数len,我们可以通过这几个元素和len将这个排列转换为一个十进制数 

上面所说的是康拓展开能解决的问题!



康拓逆展开生成全排列



既然我们可以通过排列把给出的元素转换为一个十进制数,那么肯定能通过这个这个逆向的过程,由X计算出a1,a2,a3….an。 

我们通过一个实例来解释上面所说的话,就比如上面那个解释康拓的例子,我们是否能过通过知道X=14以及元素数组{2,5,7,8}计算出a1,a2,a3,a4呢? 

在不考虑任何范围的情况下,列举不完全的下面几种情况: 

14 = 1*(3!) + 1*(2!) +1*(1!) + 1*(0!); 

14 = 2*(3!) + 2*(2!) +0*(1!) + 0*(0!); 

14 = 0*(3!) + 6*(2!) +1*(1!) + 1*(0!); 

满足情况的之有第二种情况因为最后一个数也就是a1必须是0,因为做最后只剩下一个数了,不可能再有比他小的数字了 

我们就用这种情况14 = 2*(3!) + 2*(2!) +0*(1!) + 0*(0!),来推算出一般的情况, 

1. 因为最后三个数加起来是不可能超过(3!)的,所以我们可以通过14%3!来得到a4 

2. 用14/3!的余数就是剩下的后面三个数之和,为4 

3. 然后通过4在对2!去模,就得到了a3 

4. 然后一直重复的循环1,2过程就能过依次得到an,an-1…..a1 

上面的过程也叫做辗转相除



通过上面的过程就能通过数组元素An和对应的十进制数,就能求出这个排列



解题思路



懂得了上面的理论,我们就知道可以把x的位置看做0,然后将这个数值数组通过康拓展开为一个十进制数,表示初始状态,然后一共过9!个状态,通过BFS枚举这些状态,求得转化的路径。



woshinannan741/article/details/51889245

Source

[Submit][Status]