[infobox title="P1379 八数码难题 "]
题目描述

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

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

输出格式：

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

输入输出样例
输入样例#1：

283104765

输出样例#1：

4

https://www.luogu.org/problem/show?pid=1379
[/infobox]
我的做法:
BFS不是难事，关键是记录状态和判重，要用到一个叫康托展开的哈希函数还有其逆展开..
大致思路就是把初始状态的康托展开计算出来推入队列，然后将其逆展开，交换与0相邻的元素，分别算出他们的康托展开再推入队列..
然而就是这么猥琐+丑陋又不加剪枝的算法竟然A了..
附上代码..
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 400000
#define INF 0x3f3f3f3f
using namespace std;
char s[10];
int fac[11] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362840, 3628400};//get the value before hand
int step[MAXN];
int vis[MAXN];
int a[9];
int cantor(char* a){
int can = 0;
for (int i = 0; i < 9; i++){
int tmp = 0;
for (int j = i + 1; j < 9; j++)
if (a[j] < a[i]) tmp++;
can += tmp * fac[9 - i - 1];
}

return can;
}

void uncantor(int a, char* s){
int used[10] = {0};
int j, t;
for (int i = 0; i < 9; i++){
t = a / fac[9 - i - 1];
for (j = 1; j <= 9; j++){
if (!used[j]){
if (t == 0) break;
t--;
}
}
s[i] = '0' + j - 1;
used[j] = 1;
a %= fac[9 - i - 1];
}
}
int main(){
scanf("%s", s);
memset(vis, 0, sizeof(vis));
for (int i = 0; i < MAXN; i++) step[i] = INF;
step[cantor(s)] = 0;
// cout << cantor(s) << endl;
// uncantor(cantor(s), s);
// cout << s << endl;
queue<int> q;
q.push(cantor(s));
int zr = 0;//The pos of '0'
int now, nc;
char tp[9];
while(!q.empty()){
now = q.front();
q.pop();
// cout << now << endl;
uncantor(now, tp);
vis[now] = 1;
for (int i = 0; i < 9; i++) if(tp[i] == '0') zr = i;
if (zr > 2) {//up
swap(tp[zr], tp[zr - 3]);
nc = cantor(tp);
step[nc] = min(step[nc], step[now] + 1);
if (!vis[nc]) q.push(nc);
swap(tp[zr], tp[zr - 3]);
}
if (zr < 6) {//down
swap(tp[zr], tp[zr + 3]);
nc = cantor(tp);
step[nc] = min(step[nc], step[now] + 1);
if (!vis[nc]) q.push(nc);
swap(tp[zr], tp[zr + 3]);
}
if (zr % 3 != 0) {//left
swap(tp[zr], tp[zr - 1]);
nc = cantor(tp);
step[nc] = min(step[nc], step[now] + 1);
if (!vis[nc]) q.push(nc);
swap(tp[zr], tp[zr - 1]);
}
if (zr % 3 != 2) {//right
swap(tp[zr], tp[zr + 1]);
nc = cantor(tp);
step[nc] = min(step[nc], step[now] + 1);
if (!vis[nc]) q.push(nc);
swap(tp[zr], tp[zr + 1]);
}
}
cout << step[46685] << endl;//the hash of '123804765'(the final state) is 46685 = =!
}
[/code]
第一次用到哈希??