C语言算法BFS+HASH是什么

即将参加NOIP，在VIJOS上很多题目都说可以用BFS+hash算法

宽搜当然知道，可是把hash加进来是什么意思？求解

例题：vijos p1029

就是 康托hash判重 P1029 的所谓的hash就是 康托展开（作用是判重）

目标状态就8种
276951438
294753618
438951276
492357816
618753294
672159834
816357492
834159672

由这八个BFS扩展，总共362880种状态，共12种交换方法。

9 的全排列有 三十多万 , 利用 康托 判断出 当前搜索到的 序列 是这 三十多万个排列方式中的第几个, 以此来判重......



康托展开:
{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个 123 132 213 231 312 321代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。他们间的对应关系可由康托展开来找到。 如我想知道321是{1,2,3}中第几个大的数可以这样考虑 第一位是3，当第一位的数小于3时，那排列数小于321 如 123 213 小于3的数有1，2 所以有2*2!个 再看小于第二位2的 小于2的数只有一个就是1 所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个所以321是第6个大的数。 2*2!+1*1!是康托展开 再举个例子 1324是{1,2,3,4}排列数中第几个大的数 第一位是1小于1的数没有，是0个 0*3! 第二位是3小于3的数有1，2但1已经在第一位了所以只有一个数2 1*2! 第三位是2小于2的数是1，但1在第一位所以有0个数 0*1! 所以比1324小的排列有0*3!+1*2!+0*1!=2个 1324是第三个大数。