分析：經典的八數碼問題，這里用的是heap+A*。

A*很明顯是用那個經典的A*，heap的維護和k短路非常像。

第二個簡單A*

代碼（模仿某人的）：

constnx:array[1..9] of integer=(1,1,1,2,2,2,3,3,3);ny:array[1..9] of integer=(1,2,3,1,2,3,1,2,3);ji:array[0..9] of longint=(1,1,2,6,24,120,720,5040,40320,362880); typearr=array[1..9] of integer; varq:array[0..10000] of integer;f:array[0..10000] of arr;d:array[0..10000] of string;v:array[0..730000] of boolean;p,i,j,k,st,pp:longint;a:arr;ch:char;procedure swap(var x,y:integer); beginx:=x xor y;y:=x xor y;x:=x xor y; end;procedure swaa(var x,y:arr); vark:arr; begink:=x;x:=y;y:=k; end;procedure swas(var x,y:string); vark:string; begink:=x;x:=y;y:=k; end;procedure ok; vark:longint; begink:=0;for i:=2 to 9 doif a[i]<>0 thenfor j:=1 to i-1 doif a[j]>a[i] then inc(k);if odd(k) thenbeginwriteln('unsolvable');halt;end; end;function hash:longint; vari,j,k:longint; beginhash:=0;for i:=1 to 8 doif f[p,i]<>0 thenbegink:=0;for j:=i+1 to 9 doif (f[p,j]<f[p,i])and(f[p,j]<>0) then inc(k);hash:=hash+ji[9-i]*k;end;for i:=1 to 9 doif f[p,i]=0 thenhash:=hash+ji[9-i]*(9-i);hash:=hash+1; end;procedure up; varfa,son:longint; beginson:=p; fa:=p>>1;while fa>1 dobeginif q[son]<q[fa] thenbeginswap(q[son],q[fa]);swas(d[son],d[fa]);swaa(f[son],f[fa]);end else exit;son:=fa; fa:=son>>1;end; end;procedure down; varfa,son:longint; beginfa:=1; son:=2;while son<=p dobeginif (son<p)and(q[son+1]<q[son]) then inc(son);if q[son]<q[fa] thenbeginswap(q[son],q[fa]);swas(d[son],d[fa]);swaa(f[son],f[fa]);end else exit;fa:=son; son:=fa*2;end; end;procedure find(l,r:longint; ch:char); vari:longint; begininc(p);f[p]:=f[1];swap(f[p,l],f[p,r]);i:=hash;if v[i] thenbegindec(p);exit;end else v[i]:=true;d[p]:=d[1]+ch;q[p]:=0;for i:=1 to 9 doif f[p,i]<>0 theninc(q[p],abs(nx[i]-nx[f[p,i]])+abs(ny[i]-ny[f[p,i]]));up; end;beginfor i:=1 to 3 dofor j:=1 to 3 dobeginrepeat read(ch); until ch<>' ';inc(k);if ch='x' then continue;a[k]:=ord(ch)-48;inc(st,abs(i-nx[a[k]]));inc(st,abs(j-ny[a[k]]));end;ok;p:=1;q[1]:=st;f[1]:=a;v[hash]:=true;while p>0 dobeginif q[1]=0 thenbeginwriteln(d[1]);halt;end;for i:=1 to 9 doif f[1,i]=0 thenbegink:=i;break;end;if k-3>0 then find(k,k-3,'u');if k+3<9 then find(k,k+3,'d');if (k mod 3<>1)and(k>1) then find(k,k-1,'l');if (k mod 3<>0)and(k<9) then find(k,k+1,'r');q[1]:=q[p];d[1]:=d[p];f[1]:=f[p];q[p]:=0;d[p]:='';dec(p);down;end; end.

　　

轉載于:https://www.cnblogs.com/reflec94/archive/2011/10/20/2218440.html

總結

以上是生活随笔為你收集整理的poj 1077 eight的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。