Poj2286 The Rotation Game — IDA*/IDdfs

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

话说这道题在某份poj题目分类的文章里被评价为“难”……当我怀着被虐的心态去做的时候，我发现原来这道题真的挺水……

更水的是，这题的时间限制实在是长的不能再长了，内存限制实在是大的不能再大了……实在是不知道上海2004ACM的出题人是大脑怎么想的……

题目的算法实现很简单，我们很容易发现如果朴素地来说，这道题的整个解答树的深度和广度都是极大的，因此一般的DFS会爆时间，而BFS和A*又会爆空间，而且在判重的实现上也并不是一件非常轻而易举的事情。但是仔细思考发现最优解却分布在解答树中较浅的位置。

综合最优解深度较浅、一般方法耗费状态空间较大、判重不易这几点来说，我们一定会立即想到——迭代加深。

既然考虑迭代，那么就可以IDdfs，如果再想快一点，就IDA*（小小的加一点结点排序和估价）。逐步迭代使得我们每次迭代找到最优解后可以立即退出。

先说IDdfs：限制完深度以后就可以dfs了，但是直接dfs肯定会TLE的。

首先，既然不去整体判重，那么起码上一次拉过来这次又弄回去的现象你总可以很容易地避免吧？只需要一个变量稍加记录，若上一次操作为i，这一次就不操作i对面的。

其次，我们考虑剪枝。仔细观察发现若当前中间八个格子中出现次数最多的为k，八个格子中剩下有m个与k不同，那么要向让中间八个格子都变为k至少需要m次操作，所以若当前步数+m>限制深度，则剪枝。

我是用的以上方法就1s左右AC了。内存用了800多K。

如果还想到几百MS，那也很容易，小小地来个扩展结点的排序，每次扩展枚举八个操作时，对八个操作来个估价，按顺序扩展就行了。不过我懒得写这个了。

Source Code

Problem: 2286		User: lydliyudong
Memory: 856K		Time: 1188MS
Language: Pascal		Result: Accepted

• Source Code

type
 arr=array[0..24]of longint;
const
 g:array[1..8,1..24]of integer=
 ((22,0,-2,0,0,0,-4,0,0,0,0,-5,0,0,0,-4,0,0,0,0,-5,0,-2,0),
  (0,22,0,-2,0,0,0,0,-5,0,0,0,-4,0,0,0,0,-5,0,0,0,-4,0,-2),
  (0,0,0,0,1,1,1,1,1,1,-6,0,0,0,0,0,0,0,0,0,0,0,0,0),
  (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,-6,0,0,0,0),
  (0,2,0,5,0,0,0,0,4,0,0,0,5,0,0,0,0,4,0,0,0,2,0,-22),
  (2,0,4,0,0,0,5,0,0,0,0,4,0,0,0,5,0,0,0,0,2,0,-22,0),
  (0,0,0,0,0,0,0,0,0,0,0,0,0,6,-1,-1,-1,-1,-1,-1,0,0,0,0),
  (0,0,0,0,6,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0));
 p:array[1..8]of integer=(7,8,9,12,13,16,17,18);
 s:array[1..8]of char=('A','B','C','D','E','F','G','H');
 opp:array[1..8]of integer=(6,5,8,7,2,1,4,3);
var
 a,b,now:arr;
 ans:ansistring;
 fig,i,ID:longint;
 find:boolean;

function scanf:boolean;
 begin
  for i:=1 to 24 do
   begin
    read(a[i]);
    if a[i]=0 then exit(false);
   end;
  exit(true);
 end;

function check:longint;
 var
  i:longint;
 begin
  fillchar(b,sizeof(b),0);
  for i:=1 to 8 do inc(b[now[p[i]]]);
  fig:=1;
  if b[2]>b[1] then begin b[1]:=b[2]; fig:=2; end;
  if b[3]>b[1] then begin b[1]:=b[3]; fig:=3; end;
  exit(8-b[1]);
 end;

procedure IDAstar(step,last:longint);
 var
  i,j,min:longint;
  c:arr;
 begin
  min:=check;
  if min=0 then
   begin
    find:=true;
    exit;
   end;
  if step+min>ID then exit;
  for i:=1 to 8 do
   if i<>last then
    begin
     c:=now;
     for j:=1 to 24 do now[j+g[i,j]]:=c[j];
     ans:=ans+s[i];
     IDAstar(step+1,opp[i]);
     if find then exit;
     delete(ans,length(ans),1);
     now:=c;
    end;
 end;

begin
 repeat
  if not scanf then break;
  now:=a;
  if check=0 then
   begin
    writeln('No moves needed');
    writeln(fig);
    continue;
   end;
  ID:=0;
  find:=false;
  while not find do
   begin
    inc(ID);
    now:=a;
    ans:='';
    IDAstar(0,0);
   end;
  writeln(ans);
  writeln(fig);
 until false;
end.