题解 - Vijos

0

sxpeter LV 8 @ 2008-08-30 17:23:41

分析：运用深度搜索的方法求解该问题。对棋盘中的格子从上到下从左到右依次编号1..nm，划分成nm个阶段。每个阶段有5种可能的状态，分别为放题目中的四种图形和不放置图形。放置图形时，使题目中图形的灰色格子与当前编号的格子对齐，以阶段1为例，下图列出了其中4种可能的状态。

对于任意阶段，若待扩展的状态中图形超出边界，或者重叠，则视为不合法。例如（4）图形超出边界，因此不对该状态扩展下一阶段。

因为编号是从上到下有序的，且用于覆盖的L型图形的放置点位于图形最上方，所以，任意阶段都无法覆盖到编号比它小的格子。若在某个阶段留下空白，则以后的状态都无法覆盖这个空白，无法形成完整的覆盖。因此，在扩展过程中，只有目前编号格子为已覆盖格子时，才扩展“不放置”这一状态。

若旋转90度、180度、270度后与其他方案相同的解，被认为是本质相同的解。实际上，只需要构建一个右转90度的过程，4次调用该过程即可生成4种角度旋转后的方案。如图所示，设棋盘为n*m的矩阵D，右转90度后的矩阵为D’，则D’(i,j):=D(n+1-j,i)。

关于判重可能也许有些选手会采用将以前得到的覆盖方式全记录下来，然后与当前的覆盖方式旋转作比较，这样既费时，也费空间，必然超时，所以我们采用新的判重方式：

对于由一种解旋转生成的4种或2种（长方形2种，正方形4种）方案，自定义规则对它们排序，并将顺序最小的那种方案称为最小方案。显然本质不同的解只需要求出所有的最小方案，因此对于新产生的解，旋转4次后判断它是不是最小方案，如果是则计数。

什么意思呢？我们先将拼图块编上号，设为1号，为2号，为3号，为4号。举个例子吧：如果数据为4 *4，那么不加判重可以得出3个解：

1222 2224 3333

1233 2444 1313

1143 2224 1313

4443 2444 1111

我们发现，第2和第3个答案旋转后实质上是一样的，而第2种是它旋转生成的4种方案中最小的一种，而第3种不是，因此算第2种。

为了便于大家理解，这里贴出标程：

program rqnoj237;

type arr=array[1..20,1..20]of integer;

var i,j,t,n,m:longint;

a:arr;

procedure ping(x,y:longint);forward;

procedure t1(x,y:longint);//拼第1块拼图

begin

if y>m-1 then exit;

if x>n-2 then exit;

if a[x+1,y]>0 then exit;

if a[x+2,y]>0 then exit;

if a[x+2,y+1]>0 then exit;

a[x,y]:=1;

a[x+1,y]:=1;

a[x+2,y]:=1;

a[x+2,y+1]:=1;

if y=m then ping(x+1,1)else ping(x,y+1);

a[x,y]:=0;

a[x+1,y]:=0;

a[x+2,y]:=0;

a[x+2,y+1]:=0;

end;

procedure t2(x,y:longint);//拼第2块拼图

begin

if y>m-2 then exit;

if x>n-1 then exit;

if a[x+1,y]>0 then exit;

if a[x,y+1]>0 then exit;

if a[x,y+2]>0 then exit;

a[x,y]:=2;

a[x,y+1]:=2;

a[x+1,y]:=2;

a[x,y+2]:=2;

if y=m then ping(x+1,1)else ping(x,y+1);

a[x,y]:=0;

a[x,y+1]:=0;

a[x+1,y]:=0;

a[x,y+2]:=0;

end;

procedure t3(x,y:longint);//拼第3块拼图

begin

if y>m-1 then exit;

if x>n-2 then exit;

if a[x,y+1]>0 then exit;

if a[x+1,y+1]>0 then exit;

if a[x+2,y+1]>0 then exit;

a[x,y]:=3;

a[x,y+1]:=3;

a[x+1,y+1]:=3;

a[x+2,y+1]:=3;

if y=m then ping(x+1,1)else ping(x,y+1);

a[x,y]:=0;

a[x,y+1]:=0;

a[x+1,y+1]:=0;

a[x+2,y+1]:=0;

end;

procedure t4(x,y:longint);//拼第4块拼图

begin

if yn-1 then exit;

if a[x+1,y]>0 then exit;

if a[x+1,y-1]>0 then exit;

if a[x+1,y-2]>0 then exit;

a[x,y]:=4;

a[x+1,y]:=4;

a[x+1,y-1]:=4;

a[x+1,y-2]:=4;

if y=m then ping(x+1,1)else ping(x,y+1);

a[x,y]:=0;

a[x+1,y]:=0;

a[x+1,y-1]:=0;

a[x+1,y-2]:=0;

end;

function small(var a,b:arr):boolean;//判断哪种方式更小

var i,j:longint;

begin

small:=false;

for i:=1 to n do

for j:=1 to m do

begin

if ab then exit;

end;

end;

procedure turn(var g:arr);//旋转90度

var i,j:longint;

h:arr;

begin

h:=g;

for i:=1 to m do

for j:=1 to n do

g:=h[n+1-j,i] mod 4+1;

i:=n; n:=m; m:=i;

end;

procedure Check;//判重

var i,j:longint;

h:arr;

begin

h:=a;

if n=m then

for i:=1 to 4 do

begin

if (i>1) and small(h,a) then exit;

turn(h);

end

else

for i:=1 to 2 do

begin

if (i>1) and small(h,a) then exit;

turn(h); turn(h);

end;

inc(t);

end;

procedure ping(x,y:longint);//拼图

var i,j:longint;

begin

if(x=n+1)and(y=1)then check

else

begin

if a[x,y]>0 then

begin

if y=m then ping(x+1,1)

else ping(x,y+1);

end

else

begin

t1(x,y);

t2(x,y);

t3(x,y);

t4(x,y);

end;

end;

end;