题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043 , 康托展开 + BFS + 打表。
经典八数码问题，传说此题不做人生不完整，关于八数码的八境界：http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html
我自己是用哈希(康托展开) + BFS + 打表过的，第三重境界。
由于一些高级的搜索现在还没学，所以目前能升级的也就是用双向BFS来做了，等过几天有心情了来做。
本文长期更新。
算法：
由于此题是求某个起始状态到“12345678X”的步骤，所以可以考虑先求出“12345678X”的所有变换的步骤，即打表预处理。
这里要注意就是最后输出的时候，由于我们求得是逆序，所以要倒序输出，倒序输出的时候要注意'u'、'd'、'l'、'r'都应该颠倒过来，比如说你从A状态向上变换为B状态，这时你从B变为A就要向下变换。
这里哈希还是用的康托展开，这个问题我在上一篇博客中有提到过。
BFS + 打表：
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF 1e8
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = ;
const int maxn = ;
bool vis[maxn];
string ans[maxn];
int fac[]={ , , , , , , , , , }; int Cantor(string str)
{
int ret = ;
int n = str.size();
for(int i = ; i < n ; i++) {
int cnt = ;
for(int j = i ; j < n ; j++)
if(str[j] < str[i])
cnt++;
ret += cnt * fac[n - i - ];
}
return ret;
}
void move_Up(string &str , int pos)
{
swap(str[pos] , str[pos - ]);
}
void move_Down(string &str , int pos)
{
swap(str[pos] , str[pos + ]);
}
void move_Left(string &str , int pos)
{
swap(str[pos] , str[pos - ]);
}
void move_Right(string &str , int pos)
{
swap(str[pos] , str[pos + ]);
}
void BFS(string start)
{
memset(vis , , sizeof(vis));
queue <string> que;
que.push(start);
int x = Cantor(start);
vis[x] = ;
ans[x] = "";
int pos;
while(!que.empty()) {
string u = que.front();
que.pop();
int i = Cantor(u);
for(pos = ; pos < ; pos++)
if(u[pos] == 'x')
break; if(pos > ) {
string tmp = u;
move_Up(tmp , pos);
int k = Cantor(tmp);
if(!vis[k]) {
vis[k] = ;
que.push(tmp);
ans[k] = ans[i] + 'u';
}
}
if(pos < ) {
string tmp = u;
move_Down(tmp , pos);
int k = Cantor(tmp);
if(!vis[k]) {
vis[k] = ;
que.push(tmp);
ans[k] = ans[i] + 'd';
}
}
if(pos % != ) {
string tmp = u;
move_Left(tmp , pos);
int k = Cantor(tmp);
if(!vis[k]) {
vis[k] = ;
que.push(tmp);
ans[k] = ans[i] + 'l';
}
}
if(pos % != ) {
string tmp = u;
move_Right(tmp , pos);
int k = Cantor(tmp);
if(!vis[k]) {
vis[k] = ;
que.push(tmp);
ans[k] = ans[i] + 'r';
}
}
}
}
int main()
{
char ch[];
string start = "12345678x";
BFS(start);
while(gets(ch))
{
string str = "";
for(int i = ; ch[i] != '\0' ; i++) {
if(ch[i] == ' ')
continue;
else
str += ch[i];
}
int k = Cantor(str);
if(vis[k]) {
for(int i = ans[k].size() - ; i >= ; i--) {
if(ans[k][i] == 'u')
putchar('d');
else if(ans[k][i] == 'd')
putchar('u');
else if(ans[k][i] == 'l')
putchar('r');
else
putchar('l');
}
puts("");
} else {
cout << "unsolvable" << endl;
}
}
return ;
}