八数码难题

题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

283104765

样例输出 Sample Output

数据范围及提示 Data Size & Hint

详见试题

解题思路

由题意得（讨厌这句话），这是一道搜索题，由于是找最少移动次数，所以应该是用广度优先搜索，为了节约时间，采用双向宽度优先搜索。当然，这是我第一次写双向宽搜，

应该有优化，但我并不知道怎么写，话说还有一个叫A*的算法……不造如何做！！！

  1 program EigntNumber;
  2 const f1:array[1..3,1..3] of longint=((1,2,3),
  3                                       (8,0,4),
  4                                       (7,6,5));
  5 type zz=array[1..3,1..3] of longint;
  6 const fx:array[1..4] of longint=(1,-1,0,0);
  7        fy:array[1..4] of longint=(0,0 ,1, -1);
  8 var b:array[1..2,1..100000] of zz;
  9     t,h:array[1..2] of longint;
 10     pace:array[1..2,1..100000] of longint;
 11     i,j:Longint;
 12     ch:char;
 13     f:zz;
 14 function pd(h,l:longint):boolean;
 15 begin
 16     if h>3 then exit(false);
 17     if h<=0 then exit(false);
 18     if l>3 then exit(false);
 19     if l<=0 then exit(false);
 20     exit(true);
 21 end;
 22 
 23 function check(z:zz; a:longint):longint;
 24 var i:longint;
 25 begin
 26     if a=2 then a:=1 else a:=2;
 27     for i:=1 to t[a] do
 28     if comparedword(b[a,i],z,9)=0 then exit(pace[a,i]);
 29     exit(0);
 30 end;
 31 
 32 
 33 function kg(z:zz; a:longint):boolean;//应该有优化，但是我不会写
 34 var i:Longint;
 35 begin
 36     for i:=1 to t[a] do
 37     if comparedword(b[a,i],z,9)=0 then exit(false);
 38     exit(true);
 39 end;
 40 
 41 procedure expend(a:longint);
 42 var i,j,x,y:longint;
 43     z:zz;
 44 
 45 begin
 46     inc(h[a]);
 47     for i:=1 to 3 do
 48         for j:=1 to 3 do
 49         if b[a][h[a]][i][j]=0 then
 50         begin
 51             x:=i;
 52             y:=j;
 53             break;
 54         end;
 55     for i:=1 to 4 do
 56         if pd(x+fx[i],y+fy[i]) then
 57         begin
 58             z:=b[a,h[a]];
 59             z[x,y]:=z[x+fx[i],y+fy[i]];
 60             z[x+fx[i],y+fy[i]]:=0;
 61             if check(z,a)<>0 then
 62             begin
 63                 writeln(check(z,a)+pace[a,h[a]]+1);
 64                 halt;
 65             end;
 66             if kg(z,a) then
 67             begin
 68                 inc(t[a]);
 69                 b[a,t[a]]:=z;
 70                 pace[a,t[a]]:=pace[a,h[a]]+1;
 71             end;
 72         end;
 73 end;
 74 
 75 begin
 76     for i:=1 to 3 do
 77         for j:=1 to 3 do
 78         begin
 79             read(ch);
 80             f[i,j]:=ord(ch)-48;
 81         end;
 82 
 83     b[1,1]:=f;
 84     b[2,1]:=f1;
 85     t[1]:=1;
 86     t[2]:=1;
 87     while (h[1]<=t[1]) or (h[2]<=t[2]) do
 88     begin
 89         if (t[1]<=t[2]) and (h[1]<=t[1])then
 90         begin
 91            expend(1);
 92            continue;
 93         end;
 94         if (t[1]>=t[2]) and (h[2]<=t[2]) then
 95         begin
 96                 expend(2);
 97                 continue;
 98         end;
 99         if h[1]<=t[1] then
100         expend(1);
101         if h[2]<=t[2] then
102         expend(2);
103     end;
104 end.