一般的说,这个优先队列应该怎么实现才最为高效简洁?
我用的是最小堆,然后写了6K左右……
program Eightnum_Evalver;
type statet=array[1..9] of longint;
nodet=record
m:statet; //map
h,p,e:longint; //Height,Position,Evalution
end;
const finale:statet=(1,2,3,8,0,4,7,6,5);
f:array[1..9] of longint=(1,2,6,24,120,720,5040,40320,362880);
var vis:array[1..400000] of boolean;
heap:array[1..400000] of nodet;
oute:array[1..400000] of longint;
size:longint;
head,tail:nodet;
tmp:char;
function hash(q:statet):longint;
var i,j,t:longint;
begin
hash:=0;
for i:=1 to 8 do begin
t:=0;
for j:=i+1 to 9 do
if q[j]<q[i] then inc(t);
inc(hash,f[9-i]*t);
end;
inc(hash);
end;
function finish(q:statet):boolean;
var i:longint;
begin
for i:=1 to 9 do
if q[i]<>finale[i] then exit(false);
exit(true);
end;
function eval(q:nodet):longint; //choose minium
var i,j:longint;
begin
j:=0; eval:=q.h;
for i:=1 to 9 do
if q.m[i]<>finale[i] then inc(eval);
end;
procedure init;
var i,j:longint;
begin
for i:=1 to 9 do begin
read(tmp);
head.m[i]:=ord(tmp)-48;
if tmp='0' then head.p:=i;
end;
with head do begin
h:=0;
e:=eval(head);
end;
size:=1;
heap[1]:=head;
vis[hash(head.m)]:=true;
if finish(head.m) then begin
writeln(head.h);
halt;
end;
end;
procedure bfs;
var i,j,vhash:longint;
procedure siftdown(i:longint);
var kid:longint;
valu:nodet;
begin
valu:=heap[i]; kid:=i*2;
while kid<=size do begin
if (heap[kid+1].e<heap[kid].e)and(kid<size) then inc(kid);
if heap[kid].e<valu.e then begin
heap[i]:=heap[kid];
i:=kid; kid:=i*2;
end else break;
end;
heap[i]:=valu; oute[i]:=valu.e;
end;
procedure siftup(i:longint);
var dad:longint;
valu:nodet;
begin
valu:=heap[i]; dad:=i div 2;
while dad>=1 do begin
if valu.e<heap[dad].e then begin
heap[i]:=heap[dad];
i:=dad; dad:=i div 2;
end else break;
end;
heap[i]:=valu; oute[i]:=valu.e;
end;
function extract:nodet;
begin
extract:=heap[1];
heap[1]:=heap[size];
dec(size);
siftdown(1);
end;
procedure insert(q:nodet);
begin
inc(size);
heap[size]:=q;
siftup(size);
end;
begin
while size>0 do begin
head:=extract;
if head.p>3 then begin
tail.m:=head.m;
tail.m[head.p]:=tail.m[head.p-3];
tail.m[head.p-3]:=0;
vhash:=hash(tail.m);
if not vis[vhash] then begin
vis[vhash]:=true;
tail.p:=head.p-3;
tail.h:=head.h+1;
tail.e:=eval(tail);
insert(tail);
if finish(tail.m) then begin
writeln(tail.h);
halt;
end;
end;
end;
if head.p<7 then begin
tail.m:=head.m;
tail.m[head.p]:=tail.m[head.p+3];
tail.m[head.p+3]:=0;
vhash:=hash(tail.m);
if not vis[vhash] then begin
vis[vhash]:=true;
tail.p:=head.p+3;
tail.h:=head.h+1;
tail.e:=eval(tail);
insert(tail);
if finish(tail.m) then begin
writeln(tail.h);
halt;
end;
end;
end;
if head.p mod 3 <>1 then begin
tail.m:=head.m;
tail.m[head.p]:=tail.m[head.p-1];
tail.m[head.p-1]:=0;
vhash:=hash(tail.m);
if not vis[vhash] then begin
vis[vhash]:=true;
tail.p:=head.p-1;
tail.h:=head.h+1;
tail.e:=eval(tail);
insert(tail);
if finish(tail.m) then begin
writeln(tail.h);
halt;
end;
end;
end;
if head.p mod 3 <>0 then begin
tail.m:=head.m;
tail.m[head.p]:=tail.m[head.p+1];
tail.m[head.p+1]:=0;
vhash:=hash(tail.m);
if not vis[vhash] then begin
vis[vhash]:=true;
tail.p:=head.p+1;
tail.h:=head.h+1;
tail.e:=eval(tail);
insert(tail);
if finish(tail.m) then begin
writeln(tail.h);
halt;
end;
end;
end; //Expand
end;
end;
{Main}
begin
init;
bfs;
end.