八数码难题（wikioi1225）
【题目描述】
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
【输入描述】
输入初试状态，一行九个数字，空格用0表示。
【输出描述】
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)。
【样例输入 】
283104765
【样例输出】
4
分析：
很经典题目，题意不解释了。
看到最小步骤会想到广搜，本题可以看成是空格移动达到目标状态的问题，记录空格位置和棋盘状态，加入队列不断增加节点入队。同时注意判重，将棋盘转换为九位数（如果第一个数字为0则是八位数），用hash表解决。这样就可以过这道题了。
但是为了达到更好的时间效率，可以使用双向广搜。
双向宽搜，顾名思义就是从两边搜，适用于已知起始状态和目标状态，求最短步骤的题目。
我们可以开两类数组，分别表示正方方向搜索的队列，然后初始，目标状态分别入对应队列，进行扩展节点，直到两个方向搜索相遇时即得出最短步骤。
出于优化时间的目的，我们往往先搜队列中节点少的方向，轮流进行。
具体讲就是：两个方向根据队列中节点数交替扩展节点，每扩展一个节点为，在本队列判重后还要在另一个方向的队列中找是否出现，出现说明相遇，输出最短步骤为正方方向扩展到该节点所需最短步骤。
注意双向广搜时，反方向扩展节点时操作与正方向相反，比如向左移动要变为向右移动，但这点对本题没有影响。
解释一下
head,tail表示队头队尾指针，v表示最短步骤，w是棋盘状态，px,py表示空格位置。
0表示正方向，1表示反方向。彼此可用1-x转换。
以下就是自己写的了双向广搜+hash判重的八数码AC程序。
代码
program puzzle;
const
maxn=;
type
hh=^node;
node=record
data:longint;
text:longint;
next:hh;
end;
var
dx:array[..]of longint=(,,,-);
dy:array[..]of longint=(,-,,);
hash:array[..,..maxn]of hh;
head,tail:array[..]of longint;
w:array[..,..,..,..]of longint;
b:array[..,..]of longint;
px,py,v:array[..,..]of longint;
n,i,m,j,x,y,s,h,t,k,r:longint;
c:char;
function haha(t,x:longint):boolean;
var i,j,xx:longint;p:hh;
begin
xx:=x mod maxn;
new(p);
p:=hash[t,xx];
while p<>nil do
begin
if p^.data=x then begin r:=p^.text; exit(true); end;
p:=p^.next;
end;
exit(false);
end;
procedure put(t,x:longint);
var q:hh;xx:longint;
begin
xx:=x mod maxn;
new(q);
q^.data:=x; q^.text:=tail[t]; q^.next:=hash[t,xx];
hash[t,xx]:=q;
end;
procedure bfs(x:longint);
var i,j,u,l,ans,xx,yy,g,tmp:longint;
begin
head[x]:=head[x]+;
for i:= to do
begin b:=w[x,head[x]];
xx:=px[x,head[x]]+dx[i]; yy:=py[x,head[x]]+dy[i];
tmp:=b[xx,yy];
b[xx,yy]:=b[px[x,head[x]],py[x,head[x]]];
b[px[x,head[x]],py[x,head[x]]]:=tmp;
g:=; ans:=;
for u:= to do begin
for l:= to do
begin ans:=ans+g*b[u,l]; g:=g div ; end;
end;
if (xx>)and(xx<=)and(yy>)and(yy<=)and(haha(x,ans)=false) then
begin
tail[x]:=tail[x]+; px[x,tail[x]]:=xx; py[x,tail[x]]:=yy;
w[x,tail[x]]:=b; v[x,tail[x]]:=v[x,head[x]]+; put(x,ans);
if haha(-x,ans)=true then
begin
writeln(v[x,tail[x]]+v[-x,r]); k:=; break;
end;//在另一个方向的队列中查找该节点
end;
if k= then break;
end;
if k= then exit;
end;
begin
t:=;
for i:= to do begin
for j:= to do
begin read(c);if c='' then begin x:=i; y:=j;end;
w[,,i,j]:=ord(c)-; s:=s+w[,,i,j]*t; t:=t div ; end;
end;
put(,); put(,s); k:=;//存入两个hash数组
w[,,,]:=; w[,,,]:=; w[,,,]:=;
w[,,,]:=; w[,,,]:=; w[,,,]:=;
w[,,,]:=; w[,,,]:=; w[,,,]:=;
v[,]:=; v[,]:=; px[,]:=; py[,]:=; px[,]:=x; py[,]:=y;
head[]:=; head[]:=; tail[]:=; tail[]:=;
repeat
if (tail[]>head[])and((tail[]-head[]<tail[]-head[])or(tail[]<=head[]))
then bfs()
else if tail[]>head[] then bfs();//交替扩展节点
if k= then break;
until ((head[]>=tail[])or(tail[]>=))and((head[]>=tail[])or(tail[]>=));
end.
使用双向广搜，时间效率大大提高，两种方法在不加其它优化的时间效率对比
广搜+hash
双向广搜+hash