完美覆盖
有一个n行m列的棋盘,以1×2的多米诺骨牌去覆盖n×m的棋盘。当棋盘中的每一个格子都只被一块多米诺骨牌覆盖时,这种覆盖叫多米诺骨牌的完美覆盖。如下图所示,2行3列的棋盘,有3种完美覆盖方案。
以下程序求得总方案数。程序从第1行第1列开始,以行优先的顺序逐格尝试各格子的不同覆盖方案。
rogram cz2011_6;
const maxn=100;maxm=100;
var
n,m,i,j:longint;
ans:extended;
f:array[1..maxn,1..maxm]of longint;
procedure domino(i,j:longint);
begin
if i>n then begin
ans:=ans+1 ;
exit;
end;
if f[i,j]<>0 then
begin
if j<m then
domino(i,j+1)
else
domino( i+1,j );
end
else
begin
if (f]i,j]=0) and (f[i,j+1]=0) then
begin
f[i,j]:=1;
f[i,j+1]:=1;
if j<m then
domino(i,j+1)
else
domino( i+1,j );
f[i,j]:=0;f[i,j+1]:=0;
end;
if (f]i,j]=0) and (f[i+1,j]=0) then
begin
f[i,j]:=2;
f[i+1,j]:=2;
if j<m then
domino(i,j+1)
else
domino( i+1,j );
f[i,j]:=0;f[i+1,j]:=0;
end;
end;
end;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
f[i,j]:=0;
ans:=0;
domino( 1,1 );
writeln(ans:0:0);
end.