Poj1084 Square Destroyer — IDdfs/IDA*

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

题目大意：给定一个由火柴棒拼成的n*n的网格图(去掉其中一些边)，问再去掉多少跟火柴后可以使得图中不含有大小正方形。

解法：

1.IDdfs：这是我用的解法，写起来比较简单比较好想，但是我一直不大细心，纠结了半个下午+半个晚上……= =|

从小正方形往大正方形搜，每次只找一个，枚举去掉它的哪条边界，都枚举完后退出。使用迭代加深就不会TLE。

本体数据较弱，这种方法跑5 0要超时。

2.IDA*：杜神牛用的解法，5 0乃至6 0的数据都秒杀。大致思路跟上一种差不多，就是多了估价函数，估价时这样估：找一个还没有破坏的正方形，去掉它的所有边界，但是只记作一步，统计出全部破坏需要多少步，加上当前已走步数，作为估计值。（杜神牛的奇特想法，经过试验貌似评估的还相当准确，Orz）

3.DancingLinks：火柴作为行，正方形作为列，边界相连的地方赋为1，求01覆盖。

IDA*解法：

Source Code

Problem: 1084		User: lydliyudong
Memory: 904K		Time: 32MS
Language: Pascal		Result: Accepted

• Source Code

type
 arr=array[0..60]of integer;
var
 a,b:array[0..60,0..60]of longint;
 c,d:arr;
 t,n,ID,tot,i,j,k,x:longint;

procedure push(tot,now:longint);
 begin
  inc(a[tot,0]); a[tot,a[tot,0]]:=now;
  inc(b[now,0]); b[now,b[now,0]]:=tot;
 end;

procedure prework;
 var
  temp,i,j,k,l:longint;
  con:boolean;
 begin
  tot:=0;
  for k:=0 to n-1 do
   for i:=1 to n do
    for j:=1 to n do
     if (i+k<=n)and(j+k<=n) then
      begin
       temp:=1+(i-1)*(n+n+1)+j-1;
       inc(tot);
       for l:=0 to k do
        begin
         push(tot,temp+l);
         push(tot,temp+(k+1)*(n+n+1)+l);
         push(tot,temp+n*(l+1)+(n+1)*l);
         push(tot,temp+n*(l+1)+(n+1)*l+k+1);
        end;
      end;
 end;

function calc(c,d:arr):longint;
 var
  i,j,k,x:longint;
 begin
  calc:=0;
  for i:=1 to tot do
   if d[i]=-1 then
    begin
     inc(calc);
     d[i]:=0;
     for j:=1 to a[i,0] do
      if c[a[i,j]]=-1 then
       begin
        x:=a[i,j];
        c[x]:=0;
        for k:=1 to b[x,0] do d[b[x,k]]:=0;
       end;
    end;
 end;

function IDAstar(dep:longint):boolean;
 var
  h,p,i,j,x:longint;
 begin
  h:=calc(c,d);
  if h=0 then exit(true);
  if dep+h>ID then exit(false);
  for i:=1 to tot do
   if d[i]=-1 then
    begin p:=i; break; end;
  d[p]:=dep;
  for i:=1 to a[p,0] do
   if c[a[p,i]]=-1 then
    begin
     x:=a[p,i];
     c[x]:=dep;
     for j:=1 to b[x,0] do
      if d[b[x,j]]=-1 then d[b[x,j]]:=dep;
     if IDAstar(dep+1) then exit(true);
     for j:=1 to b[x,0] do
      if d[b[x,j]]=dep then d[b[x,j]]:=-1;
     c[x]:=-1;
    end;
  d[p]:=-1;
  exit(false);
 end;

begin
 read(t);
 repeat
  dec(t);
  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);
  fillchar(c,sizeof(c),255);
  fillchar(d,sizeof(d),255);
  read(n);
  prework;
  read(k);
  for i:=1 to k do
   begin
    read(x);
    c[x]:=-2;
    for j:=1 to b[x,0] do d[b[x,j]]:=-2;
   end;
  for ID:=0 to 8*n do
   if IDAstar(0) then break;
  writeln(ID);
 until t=0;
end.