经典的八数码问题，用来练习各种搜索=_=。这题我用的A*做的，A*的主要思想就是在广搜的时候加了一个估价函数，用来评估此状态距离最终状态的大概距离。这样就可以省下很多状态不用搜索。对于每个状态设置一个函数 h(x)，这就是估价函数了（可能名词不太对请见谅），再设置一个函数 g(x)， 这存的是初始状态到当前状态所用步数（或距离，视估价函数而定），再设函数 f(x) = g(x) + h(x)，我们对每个状态的 f(x)的值进行排序， 然后从当前 f(x) 最小的状态继续搜索，直到搜索到最终状态或者没有后继状态。
上代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 10
#define M 500000
using namespace std; struct sss
{
int state[N];
int num, place;
};
priority_queue<sss> q; int f[M], g[M] = {}, fa[M] = {}, move[M] = {};
sss begin, end;
int step[][] = {{-,},{,-},{,},{,}};
int color[M] = {}; bool operator < (sss a, sss b) { return f[a.num] > f[b.num]; }
bool operator == (sss a, sss b) { return a.num == b.num; } int h(sss a) // h(v)
{
int z = ;
for (int i = ; i <= ; ++i)
for (int j = ; j <= ; ++j)
{
int x = (i-)*+j;
z += abs(i-(a.state[x]-)/) + abs(j-(a.state[x]-(a.state[x]-)/*));
}
return z;
} int jiecheng[N] = {,,,,,,,,,};
int make_num(sss a) // 康拓展开
{
int ans = ; bool xiao[N] = {};
for (int i = ; i <= ; ++i)
{
int count = ; xiao[a.state[i]] = ;
for (int j = ; j < a.state[i]; ++j)
if (!xiao[j]) count++;
ans += count * jiecheng[N-i-];
}
return ans;
} bool in(sss now, int mo) // 移动可行
{
int x = (now.place-)/+, y = now.place-(x-)*;
x += step[mo-][]; y += step[mo-][];
if (x < || x > || y < || y > ) return false;
else return true;
} void A_star() // A*
{
q.push(begin); f[begin.num] = h(begin);
while (!q.empty())
{
sss u = q.top(); q.pop();
if (u == end)
return;
for (int i = -; i <= ; i+=)
{
if (!in(u,(i+)/)) continue;
sss v; v = u; swap(v.state[u.place+i], v.state[u.place]);
v.place = u.place + i; v.num = make_num(v);
if (color[v.num] == )
{
if (g[u.num] + < g[v.num])
{
f[v.num] = f[v.num] - g[v.num] + g[u.num] + ;
g[v.num] = g[u.num] + ; move[v.num] = i;
q.push(v); fa[v.num] = u.num;
}
}
else if (color[v.num] == )
{
if (g[u.num] + < g[v.num])
{
f[v.num] = f[v.num] - g[v.num] + g[u.num] + ;
g[v.num] = g[u.num] + ; fa[v.num] = u.num;
q.push(v); color[v.num] = ; move[v.num] = i;
}
}
else
{
g[v.num] = g[u.num] + ;
f[v.num] = h(v) + g[v.num];
color[v.num] = ; fa[v.num] = u.num;
q.push(v); move[v.num] = i;
}
}
color[u.num] = ;
}
} char change(int x)
{
if (x == -) return 'l';
else if (x == -) return 'u';
else if (x == ) return 'r';
else return 'd';
} void print() // 输出
{
char s[M], snum = ;
int k = fa[end.num];
s[++snum] = change(move[end.num]);
while (k != begin.num)
{
s[++snum] = change(move[k]);
k = fa[k];
}
for (int i = snum; i > ; --i)
printf("%c", s[i]);
printf("\n");
} int main()
{
char s[];
for (int i = ; i <= ; ++i)
{
scanf("%s", s);
if (s[] != 'x') begin.state[i] = s[] - '';
else
{
begin.state[i] = ;
begin.place = i;
}
end.state[i] = i;
}
begin.num = make_num(begin);
end.num = make_num(end);
A_star();
print();
}