const maxn=1200007;
c:array[1..4]of longint=(-1,-3,1,3);
goal:string='123804765';
var ss,t,i,j,n,m,k,o,p:longint;
b:array[1..maxn]of longint;
sh:array[1..maxn]of string[9];
pd:boolean;
s:array[1..400000]of string[9];
a:array[1..400000]of longint;
ls:string;
kx:array[1..4]of integer;
function hash(s:string):longint;
var q:int64;
begin
val(s,q);
hash:=q mod maxn;
end;
begin
readln(s[1]);
o:=hash(s[1]);
b[o]:=1;
sh[o]:=s[1];
ss:=1;
a[1]:=0;
t:=1;
repeat
for i:=1 to 4 do kx[i]:=i;
i:=4;
p:=pos('0',s[ss]);
if p=1 then begin kx[1]:=0;kx[2]:=0;end;
if p=2 then kx[2]:=0;
if p=3 then begin kx[2]:=0;kx[3]:=0;end;
if p=4 then kx[1]:=0;
if p=6 then kx[3]:=0;
if p=7 then begin kx[1]:=1;kx[4]:=0;end;
if p=8 then begin kx[3]:=0;end;
if p=9 then begin kx[3]:=0;kx[4]:=0;end;
for i:=1 to 4 do
if kx[i]<>0 then
begin
ls:=s[ss];
ls[p]:=ls[p+c[i]];
ls[p+c[i]]:='0';
o:=hash(ls);
pd:=true;
while (o<maxn)and(b[o]=1) do
begin
if sh[o]=ls then begin pd:=false;break; end;
inc(o);
end;
if (o<=maxn)and pd then
begin
b[o]:=1;
sh[o]:=ls;
inc(t);
a[t]:=a[ss]+1;
s[t]:=ls;
if ls=goal then begin writeln(a[t]);halt;end;
end;
end;
inc(ss);
until ss>t;
end.
单向BFS+HASH,看别人这么写100,我咋TLE了?