(棋盘覆盖问题)在一个2
k×2
k个方格组成的棋盘中恰有一个方格与其它方格不同(图中标记为-1的方格),称之为特殊方格。现用L型(占3个小方格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠,于是,用到的纸片数恰好是(4
k-1)/3。在下表给出的一个覆盖方案中,k=2,相同的3各数字构成一个纸片。下面给出的程序使用分治法设计的,将棋盘一分为四,依次处理左上角、右上角、左下角、右下角,递归进行。请将程序补充完整。(图画不了...郁闷)
Program j402;
type
arr1=array[1..65] of integer;
arr2=array[1..65] of arr1;
var
board:arr2;
tile:integer;
size,dr,dc:integer;
procedure chessboard(tr,tc:integer; dr,dc:integer; var size:integer);
var t,s:integer;
begin
if (size=1) then 1 ;
t:=tile; inc(tile);
s:=size div 2;
if 2 then chessboard(tr,tc,dr,dc,s)
else
begin
board[tr+s-1]:=t;
3 ;
end;
if (dr<tr+s) and (dc>=tc+s) then chessboard(tr,tc+s,dr,dc,s)
else
begin
board[tr+s-1][tc+s]:=t;
4 ;
end;
if (dr>=tr+s) and (dc<tc+s) then chessboard(tr+s,tc+s,dr,dc,s) else
begin
board[tr+s][tc+s]:=t;
5 ;
end;
if (dr>=tr+s) and (dc>=tc+s) then chessboard(tr+s,tc+s,dr,dc,s)
else
begin
board[tr+s][tc+s]:=t;
6 ;
end;
end;
procedure prt1(n:integer);
var i,j:integer;
begin
for i:=1 to n do
begin
for j:=1 to n do write(board[j]:3);
writeln;
end;
end;
begin
writeln('input size(4/8/16/64):');
readln(size);
writeln('input the position of special block(x,y):');
readln(dr,dc);
board[dr][dc]:=-1;
tile:=1;
chessboard(1,1,dr,dc,size);
prt1(size);
end.