Poj1077 Eight — 八数码问题，A*+Heap=0ms

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

八数码问题，超级经典，某些人说此题不做人生不完整……汗|

解题思路：A*、A*+Heap、双向BFS、BFS(写的难看的话有可能TLE)……

这道题最好的方法是A*+Heap，使用曼哈顿距离和作为估价函数，利用阶乘哈希记录某一状态是否访问，0ms闪过……

还有注意本题是个SpecialJudge，我纠结了一晚上跟样例都不一样还以为自己错了……= =|

大概解释一下：

1.曼哈顿距离：也就是某位置上的数字与目标位置差几步，例如6应该在第二行第三列，而现在在第一行第一列，则曼哈顿距离为4。

我们除了空格以外所有的数字的曼哈顿距离和作为估价函数，每次取出小根堆顶元素（曼哈顿距离和最小的）扩展。

2.如何判断某一状态是否到过，防止死循环：利用这样一个哈希函数(注意：该哈希函数是可以保证状态与哈希值一一对应的！！！证明略，去翻数学书吧，很多这样的题都是利用阶乘的某些特殊性质来构造哈希函数，效果极佳，所以只需要一个boolean数组搞定)：【不是x的数字的逆序个数（后边解释）】*【(k-1)的阶乘(k指当前的数字是第k个不为x的数，具体见例子)】+【9-x的位置号】*8！。逆序个数指的是该数字前有几个数字比它大。比如数列1 2 3 5 7 4 x 6 8的hash值为：0*0!+0*1!+0*2!+0*3!+0*4!+2*5!+1*6!+0*7!+(9-7)*8!

其中4的逆序个数为2（5和7在他前面），6的逆序个数为1，其它的逆序个数为0。空格的位置为7，因此是(9-7)*8!.这种hash值一定不会超过9！的两倍。

3.队列记录估价、操作字符串、当前数码状态（直接用1~9的integer或者byte数组记录就行）

4.对于unsolveble的数据特殊处理：计算除空格外所有数字的逆序个数总和（前面在第2条里提到逆序个数的概念了），由于目标状态逆序个数为0，所以只要计算出的逆序个数总和为奇数，该数据必然无解。可以扩展为：

如果两个状态的逆序个数和奇偶性相同则这两个状态可达，否则一定不可达。

具体原因，只需要把9个格子看做一行数，左右移动看做向左或向右1个单位，上下移动看做空格与空格往前或后3个单位的那个数交换位置，不难证明这种计算是正确的。（小提示：若空格只向左或向右移动一个格子，只会改变空格和相邻数的位置，不会改变数的逆序值；若向上或向下，则等效为改变了两个数的逆序值，奇偶性仍不变）。

顺便说下，事实证明偶尔拿applepi作为函数名是很涨RP的T_T

Source Code

Problem: 1077		User: lydliyudong
Memory: 1352K		Time: 0MS
Language: Pascal		Result: Accepted

• Source Code

type
 arr=array[1..9]of integer;
const
 h:array[1..9]of integer=(1,1,1,2,2,2,3,3,3);
 c:array[1..9]of integer=(1,2,3,1,2,3,1,2,3);
 b:array[0..9]of longint=(1,1,2,6,24,120,720,5040,40320,362880);
var
 q:array[0..7000]of integer;
 f:array[0..7000]of arr;
 d:array[0..7000]of ansistring;
 v:array[0..720000]of boolean;
 a:arr;
 p,i,j,k,start,pp:longint;
 ch:char;

procedure swap(var x,y:integer);
 begin
  x:=x xor y; y:=x xor y; x:=x xor y;
 end;

procedure swaparr(var x,y:arr);
 var z:arr;
 begin
  z:=x; x:=y; y:=z;
 end;

procedure swapstr(var x,y:ansistring);
 var z:ansistring;
 begin
  z:=x; x:=y; y:=z;
 end;

function cal:longint;
 begin
  cal:=0;
  for i:=2 to 9 do
   if a[i]<>0 then
    for j:=1 to i-1 do
     if a[j]>a[i] then inc(cal);
 end;

function hash:longint;
 var
  i,j,k:longint;
 begin
  hash:=0; k:=-1;
  for i:=1 to 9 do
   begin
    if f[p,i]<>0 then inc(k);
    if f[p,i]=0 then inc(hash,(9-i)*b[8])
    else for j:=1 to i-1 do if f[p,j]>f[p,i] then inc(hash,b[k]);
   end;
 end;

procedure insert(t:longint);
 begin
  while t div 2>1 do
   if q[t]<q[t div 2] then
    begin
     swap(q[t],q[t div 2]);
     swaparr(f[t],f[t div 2]);
     swapstr(d[t],d[t div 2]);
     t:=t div 2;
    end
   else break;
 end;

procedure heapify(l,r:longint);
 var
  t:longint;
 begin
  t:=2*l;
  while t<=r do
   begin
    if (t<r)and(q[t]>q[t+1]) then inc(t);
    if q[l]>q[t] then
     begin
      swap(q[l],q[t]);
      swaparr(f[l],f[t]);
      swapstr(d[l],d[t]);
      l:=t; t:=2*l;
     end
    else break;
   end;
 end;

procedure scanf;
 begin
  for i:=1 to 3 do
  for j:=1 to 3 do
   begin
    repeat read(ch); until ch<>' ';
    inc(k);
    if ch='x' then continue;
    a[k]:=ord(ch)-ord('0');
    inc(start,abs(i-h[a[k]]));
    inc(start,abs(j-c[a[k]]));
   end;
 end;

procedure applepi(l,r:longint; ch:char);
 var
  i:longint;
 begin
  inc(p);
  f[p]:=f[1];
  swap(f[p,l],f[p,r]);
  i:=hash;
  if v[i] then begin dec(p); exit; end else v[i]:=true;
  d[p]:=d[1];
  d[p]:=d[p]+ch;
  q[p]:=0;
  for i:=1 to 9 do
   if f[p,i]<>0 then
    inc(q[p],abs(h[i]-h[f[p,i]])+abs(c[i]-c[f[p,i]]));
  insert(p);
 end;

begin
 scanf;
 if odd(cal) then begin writeln('unsolvable'); exit; end;
 p:=1;
 q[p]:=start; f[p]:=a; v[hash]:=true;
 while p>=1 do
  begin
   if q[1]=0 then begin writeln(d[1]); break; end;
   for i:=1 to 9 do if f[1,i]=0 then k:=i;
   if k-3>0 then applepi(k,k-3,'u');
   if k+3<9 then applepi(k,k+3,'d');
   if (k mod 3<>1)and(k>1) then applepi(k,k-1,'l');
   if (k mod 3<>0)and(k<9) then applepi(k,k+1,'r');
   q[1]:=q[p]; f[1]:=f[p]; d[1]:=d[p];
   q[p]:=0; d[p]:='';
   dec(p);
   heapify(1,p);
  end;
end.