终于也用pascal bfs裸过 发个代码给后来人 172MS飘过
const js:array[1..9]of longint=(43046721,4782969,531441,59049,6561,729,81,9,1);
      hj:array[1..4]of char=('u','d','r','l');
type bt=array[1..9]of 0..8;
var s:string;
    start,a:bt;
    i,l,n,z:integer;
    pd:array[0..9999991]of 0..1;
function zh(x:bt):longint;
var i:integer;
begin
 zh:=0;
 for i:=1 to 9 do zh:=zh+x[i]*js[i];
end;
procedure bfs;
var a:array[1..200000]of bt;
    b:array[1..200000]of longint;
    c:array[1..200000]of 0..4;
    d:array[1..200000]of 0..9;
    x1,x2:bt;
    open,closed,zero,bj,i,p,n:longint;
    f:array[1..4]of integer;
    g:array[1..200000]of 0..4;
procedure ins(x2:bt;ct,t:longint);
var ttt:longint;
begin
 ttt:=zh(x2)mod 9999991;
 if pd[ttt]=0 then
 begin
  pd[ttt]:=1;
  inc(closed);
  a[closed]:=x2;
  b[closed]:=open;
  c[closed]:=t;
  d[closed]:=ct;
  if ttt=4481041 then bj:=1;
 end;
end;
begin
 open:=0;closed:=1;
 a[1]:=start;
 b[1]:=0;
 c[1]:=0;
 d[1]:=z;
 bj:=0;
 pd[zh(start)mod 9999991]:=1;
 repeat
  inc(open);
  x1:=a[open];
  zero:=d[open];
  f[1]:=zero-3;
  f[3]:=zero+1;
  if(f[3]=4)or(f[3]=7)or(f[3]>9)then f[3]:=-1;
  f[2]:=zero+3;
  if f[2]>9 then f[2]:=-1;
  f[4]:=zero-1;
  if(f[4]=3)or(f[4]=6)or(f[4]<1)then f[4]:=-1;
  for i:=1 to 4 do
  if f[i]>0 then
  begin
   x2:=x1;
   p:=x2[f[i]];
   x2[f[i]]:=x2[zero];
   x2[zero]:=p;
   ins(x2,f[i],i);
   if bj=1 then break;
  end;
  if bj=1 then break;
 until(open>=closed)or(pd[4481041]=1);
 n:=0;
 while closed>0 do
 begin
  inc(n);
  g[n]:=c[closed];
  closed:=b[closed];
 end;
 dec(n);
 for i:=n downto 1 do write(hj[g[i]]);writeln;
end;
begin
 readln(s);
 l:=length(s);
 n:=0;
 for i:=1 to l do
 if s[i]in['0'..'8']then
 begin
  inc(n);
  start[n]:=ord(s[i])-48;
 end else
 if s[i]='x'then
 begin
  inc(n);
  start[n]:=0;
  z:=n;
 end;
 bfs;
end.