8数码问题

8数码问题，即在一个3×3的矩阵中有8个数（1至8）和一个空格，从一个状态转换到另一个状态，每次只能移动与空格相邻的一个数字到空格当中

AOJ-417-8数码

http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=417

这题是求转化的最少步数，可用BFS解决，共有9!=362880种情况，关键是如何标记已经访问过的状态，保证每次搜索得到的状态都是最小的步数，这里可将字符串转化成对应的整数来处理，可用康托展开来节省存储空间

康托展开: X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!
ai为在当前未出现的数字中是排在第几个（0<=ai<i）
例如3 5 7 4 1 2 9 6 8 展开为
X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884