关于tju1258双向宽搜的做法讨论 经过不懈努力,终于吧tju1258ac了 当然,初看好象是一个简单题,bfs+hash了事,不过并不是那么简单.... 一个单纯的正向宽搜程序: const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);      maxn=362880;      maxmm=3;var restate:array[1..maxn]of boolean;    queue:array[1..maxn,1..2]of longint;    mat:array[0..maxmm,1..9]of integer;    tmpline:array[1..9]of integer;    recode,tmpstate,co,qf,qr,s:longint; procedure init;begin  fillchar(restate,sizeof(restate),false);  qf:=0;qr:=0;end; procedure turncode(num:integer;var code:longint);var s,s1:integer;    sum:longint;begin  sum:=1;  for s:=1 to 9 do mat[0,s]:=mat[num,s]+1;  for s:=1 to 8 do  begin    inc(sum,(mat[0,s]-1)*dbin[9-s]);    for s1:=s+1 to 9 do if mat[0,s1]>mat[0,s]then dec(mat[0,s1]);  end;  code:=sum;end; procedure turnmat(num:integer;code:longint);var add,dnum,s,s1:integer;    tmp:longint;begin  tmp:=code-1;  for s:=8 downto 0 do  begin    if s>0 then    begin      tmpline[9-s]:=tmp div dbin[s]+1;      dnum:=tmpline[9-s];      tmp:=tmp mod dbin[s];    end else dnum:=1;    for s1:=8-s downto 1 do if dnum>=tmpline[s1] then inc(dnum);    mat[num,9-s]:=dnum-1;  end;end; procedure inqueue(d1,d2:longint);begin  inc(qr);  queue[qr,1]:=d1;  queue[qr,2]:=d2;end; procedure outqueue(var d1,d2:longint);begin  inc(qf);  if qf>qr then  begin    d1:=-1;    exit;  end;  d1:=queue[qf,1];  d2:=queue[qf,2];end; procedure change(num1,num2,op:integer);var tt:integer;begin  mat[num2]:=mat[num1];  if op=1 then  begin    tt:=mat[num2,6];mat[num2,6]:=mat[num2,5];    mat[num2,5]:=mat[num2,4];mat[num2,4]:=tt;  end else  begin    tt:=mat[num2,1];mat[num2,1]:=mat[num2,4];mat[num2,4]:=mat[num2,7];    mat[num2,7]:=mat[num2,8];mat[num2,8]:=mat[num2,9];    mat[num2,9]:=mat[num2,6];mat[num2,6]:=mat[num2,3];    mat[num2,3]:=mat[num2,2];mat[num2,2]:=tt;  end;end; beginwhile not seekeof do begin  init;  readln(mat[1,1],mat[1,2],mat[1,3]);  readln(mat[1,4],mat[1,5],mat[1,6]);  readln(mat[1,7],mat[1,8],mat[1,9]);  turncode(1,recode);  tmpstate:=recode;  inqueue(tmpstate,0);  outqueue(tmpstate,co);  while tmpstate<>-1 do  begin    if tmpstate=1 then break;    turnmat(1,tmpstate);    for s:=1 to 2 do    begin      change(1,2,s);      turncode(2,recode);      if not restate[recode] then       begin        restate[recode]:=true;        inqueue(recode,co+1);      end;    end;    outqueue(tmpstate,co);  end;  if tmpstate=-1 then writeln('UNSOLVABLE') else writeln(co);end;end. 后果显然是TLE 当时还不知道,其最大深度足有32层之多...!!!     于是,我又想到了反向宽搜,这样的好处是一次搜完: 程序如下: const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);      maxn=362880;      maxmm=2;var restate:array[1..maxn]of boolean;    numstep:array[1..maxn]of longint;    queue:array[1..maxn,1..2]of longint;    mat:array[0..maxmm,1..9]of integer;    tmpline:array[1..9]of integer;    recode,tmpstate,co,qf,qr,s:longint; procedure init;begin  qf:=0;qr:=0;end; procedure turncode(num:integer;var code:longint);var s,s1:integer;    sum:longint;begin  sum:=1;  for s:=1 to 8 do  begin    inc(sum,(mat[num,s])*dbin[9-s]);    for s1:=s+1 to 9 do if mat[num,s1]>mat[num,s]then dec(mat[num,s1]);  end;  code:=sum;end; procedure turnmat(num:integer;code:longint);var add,dnum,s,s1:integer;    tmp:longint;begin  tmp:=code-1;  for s:=8 downto 0 do  begin    if s>0 then    begin      tmpline[9-s]:=tmp div dbin[s]+1;      dnum:=tmpline[9-s];      tmp:=tmp mod dbin[s];    end else dnum:=1;    for s1:=8-s downto 1 do if dnum>=tmpline[s1] then inc(dnum);    mat[num,9-s]:=dnum-1;  end;end; procedure inqueue(d1,d2:longint);begin  inc(qr);  queue[qr,1]:=d1;  queue[qr,2]:=d2;end; procedure outqueue(var d1,d2:longint);begin  inc(qf);  if qf>qr then  begin    d1:=-1;    exit;  end;  d1:=queue[qf,1];  d2:=queue[qf,2];end; procedure change(num1,num2,op:integer);var tt:integer;begin  mat[num2]:=mat[num1];  if op=1 then  begin    tt:=mat[num2,4];mat[num2,4]:=mat[num2,5];    mat[num2,5]:=mat[num2,6];mat[num2,6]:=tt;  end else  begin    tt:=mat[num2,1];mat[num2,1]:=mat[num2,2];mat[num2,2]:=mat[num2,3];    mat[num2,3]:=mat[num2,6];mat[num2,6]:=mat[num2,9];    mat[num2,9]:=mat[num2,8];mat[num2,8]:=mat[num2,7];    mat[num2,7]:=mat[num2,4];mat[num2,4]:=tt;  end;end; begin  init;  tmpstate:=1;  restate[1]:=true;  inqueue(tmpstate,0);  outqueue(tmpstate,co);  while tmpstate<>-1 do  begin    turnmat(1,tmpstate);    for s:=1 to 2 do    begin      change(1,2,s);      turncode(2,recode);      if not restate[recode] then      begin        restate[recode]:=true;        numstep[recode]:=co+1;        inqueue(recode,co+1);      end;    end;    outqueue(tmpstate,co);  end;  writeln('done');  while not seekeof do  begin    readln(mat[1,1],mat[1,2],mat[1,3]);    readln(mat[1,4],mat[1,5],mat[1,6]);    readln(mat[1,7],mat[1,8],mat[1,9]);    turncode(1,recode);    if not restate[recode] then writeln('UNSOLVABLE') else writeln(numstep[recode]);  end;end.用一个数组记录下所有情况,以后就直接用. TLE得我郁闷. 不过,我发现了一个结论:一就是刚才所说的32层,另一个就是...没有无解情况...很奇怪吧?不过也是自然的:因为你可以试一试任何一个数都能移到其他任意位置.就是这样... 所以...Go away..."UNSOLVABLE"!!!!   很自然就想到了双向宽搜. 为了避免作弊我暂时不给出程序. 但是,我提供一些数据: 设一个反向搜索的maxdepth,则: time>2000ms(maxdepth<=12) time=1400ms(maxdepth=13) time<1s(14<=maxdepth<=31,都能ac) 从理论上说,maxdepth=32/2=16时,时间是最优的,我当时取的16,ac360ms 但是,因为是多组数据,就不一定了,经过测试,当maxdepth=18时,time<260ms   这里费了不少心血,就是把一个3*3的方阵压缩成一个1-9!的一个一一对应的数. procedure turncode(num:integer;var code:longint);var s,s1:integer;    sum:longint;begin  sum:=1;  for s:=1 to 9 do mat[0,s]:=mat[num,s]+1;  for s:=1 to 8 do  begin    inc(sum,(mat[0,s]-1)*dbin[9-s]);    for s1:=s+1 to 9 do if mat[0,s1]>mat[0,s]then dec(mat[0,s1]);  end;  code:=sum;end; procedure turnmat(num:integer;code:longint);var add,dnum,s,s1:integer;    tmp:longint;begin  tmp:=code-1;  for s:=8 downto 0 do  begin    if s>0 then    begin      tmpline[9-s]:=tmp div dbin[s]+1;      dnum:=tmpline[9-s];      tmp:=tmp mod dbin[s];    end else dnum:=1;    for s1:=8-s downto 1 do if dnum>=tmpline[s1] then inc(dnum);    mat[num,9-s]:=dnum-1;  end;end; 实际上这是一个O(40)的算法.不够好. 谁能给出更快的压缩方法请指点,如一个O(9)的 拜托了.... 给程序吧...不然有人不服气 const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);      maxn=362880;      maxmm=2;      maxbdep=16  (18); var restate:array[1..maxn]of boolean;    restate2:array[1..maxn]of boolean;    numstep:array[1..maxn]of longint;    queue:array[1..maxn,1..2]of longint;    mat:array[0..maxmm,1..9]of integer;    tmpline:array[1..9]of integer;    recode,tmpstate,co,qf,qr,s:longint; procedure init;begin  qf:=0;qr:=0;end; procedure turncode(num:integer;var code:longint);var s,s1:integer;    sum:longint;begin  sum:=1;  for s:=1 to 8 do  begin    inc(sum,(mat[num,s])*dbin[9-s]);    for s1:=s+1 to 9 do if mat[num,s1]>mat[num,s]then dec(mat[num,s1]);  end;  code:=sum;end; procedure turnmat(num:integer;code:longint);var add,dnum,s,s1:integer;    tmp:longint;begin  tmp:=code-1;  for s:=8 downto 0 do  begin    if s>0 then    begin      tmpline[9-s]:=tmp div dbin[s]+1;      dnum:=tmpline[9-s];      tmp:=tmp mod dbin[s];    end else dnum:=1;    for s1:=8-s downto 1 do if dnum>=tmpline[s1] then inc(dnum);    mat[num,9-s]:=dnum-1;  end;end; procedure inqueue(d1,d2:longint);begin  inc(qr);  queue[qr,1]:=d1;  queue[qr,2]:=d2;end; procedure outqueue(var d1,d2:longint);begin  inc(qf);  if qf>qr then  begin    d1:=-1;    exit;  end;  d1:=queue[qf,1];  d2:=queue[qf,2];end; procedure changeback(num1,num2,op:integer);var tt:integer;begin  mat[num2]:=mat[num1];  if op=1 then  begin    tt:=mat[num2,4];mat[num2,4]:=mat[num2,5];    mat[num2,5]:=mat[num2,6];mat[num2,6]:=tt;  end else  begin    tt:=mat[num2,1];mat[num2,1]:=mat[num2,2];mat[num2,2]:=mat[num2,3];    mat[num2,3]:=mat[num2,6];mat[num2,6]:=mat[num2,9];    mat[num2,9]:=mat[num2,8];mat[num2,8]:=mat[num2,7];    mat[num2,7]:=mat[num2,4];mat[num2,4]:=tt;  end;end; procedure change(num1,num2,op:integer);var tt:integer;begin  mat[num2]:=mat[num1];  if op=1 then  begin    tt:=mat[num2,6];mat[num2,6]:=mat[num2,5];    mat[num2,5]:=mat[num2,4];mat[num2,4]:=tt;  end else  begin    tt:=mat[num2,1];mat[num2,1]:=mat[num2,4];mat[num2,4]:=mat[num2,7];    mat[num2,7]:=mat[num2,8];mat[num2,8]:=mat[num2,9];    mat[num2,9]:=mat[num2,6];mat[num2,6]:=mat[num2,3];    mat[num2,3]:=mat[num2,2];mat[num2,2]:=tt;  end;end;begin  init;  tmpstate:=1;  restate[1]:=true;  inqueue(tmpstate,0);  outqueue(tmpstate,co);  while tmpstate<>-1 do  begin    turnmat(1,tmpstate);    for s:=1 to 2 do    begin      changeback(1,2,s);      turncode(2,recode);      if not restate[recode] then      begin        restate[recode]:=true;        numstep[recode]:=co+1;        if co<maxbdep then inqueue(recode,co+1);      end;    end;    outqueue(tmpstate,co);  end;  while not seekeof do  begin    init;    fillchar(restate2,sizeof(restate2),false);    readln(mat[1,1],mat[1,2],mat[1,3]);    readln(mat[1,4],mat[1,5],mat[1,6]);    readln(mat[1,7],mat[1,8],mat[1,9]);    turncode(1,recode);    tmpstate:=recode;    inqueue(tmpstate,0);    outqueue(tmpstate,co);    while tmpstate<>-1 do    begin      turnmat(1,tmpstate);      if restate[tmpstate] then break;      for s:=1 to 2 do      begin        change(1,2,s);        turncode(2,recode);        if not restate2[recode] then        begin          restate2[recode]:=true;          inqueue(recode,co+1);        end;      end;      outqueue(tmpstate,co);    end;    writeln(numstep[tmpstate]+co);  end;end.   http://bbs.cqyzedu.com/dispbbs.asp?boardid=24&id=4142  

评论