用BFS 再加上HASH判重就可以了

代码可能丑了点… 但绝对能用 o(∩_∩)o

const

c;array [0..2,1..4] of integer=((3,-3,-1,0),(3,-3,1,0),(-3,3,-1,1));

var

hash;array[1..900000] of boolean;

f;array[1..100000] of string;

d;array[1..100000] of longint;

s,e,i,p1,p2,h,c1;longint;

t;char;

p,te;string;

begin

readln(p);

f[1];=’123804765′;

d[1];=0;

s;=1;

e;=1;

repeat

p1;=pos(‘0’,f[s]);

c1;=p1 mod 3;

for i;=1 to 4 do

begin

p2;=p1+c[c1,i];

if (p2>0) and (p2<10) then

begin

te;=f[s];

t;=te[p2];

te[p2];=te[p1];

te[p1];=t;

val(te,h);

h;=h mod 99983;

if hash[h]=false then

begin

hash[h];=true;

e;=e+1;

f[e];=te;

d[e];=d[s]+1;

end;

if te=p then

begin

writeln(d[e]);

halt;

end;

end;

end;

s;=s+1;

until s>e;

end.