Question

求NOIP2007普及组初赛试题（棋盘覆盖问题）的程序解析，比如程序的思路以及每步的作用

就是这道题，望高手给予解答，给高分100哦
（棋盘覆盖问题）在一个2k × 2k 个方格组成的棋盘中恰有一个方格与其他方格不同（图中标记为-1 的方格），称之为特殊方格。现用L 型（占3 个小格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是(4k −1) / 3 。在下表给出的一个覆盖方案中，k=2，相同的3个数字构成一个纸片。
下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5
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 ⑤ ;
t:=tile; inc(tile);
s:=size div 2;
if ⑥ then
chessboard(tr,tc,dr,dc,s)
else
begin
board[tr+s-1][tc+s-1]:=t;
⑦ ;
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;
⑧ ;
end;
if(dr>=tr+s) and(dc<tc+s) then
chessboard(tr+s,tc,dr,dc,s)
else
begin
board[tr+s][tc+s-1]:=t;
⑨ ;
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;
⑩ ;
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[i][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.
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5
这就是那个图，4行4列的表格中的数据
参考答案是：⑤ exit
⑥ (dr<tr+s)and(dc<tc+s)
⑦ chessboard(tr,tc,tr+s-1,tc+s-1,s)
⑧ chessboard(tr,tc+s,tr+s-1,tc+s,s)
⑨ chessboard(tr+s,tc,tr+s,tc+s-1,s)
⑩ chessboard(tr+s,tc+s,tr+s,tc+s,s)
但是看不明白，请高手指点

Answer 1

声明：本文使用的代码和例子的来源：《计算机算法设计与分析》（王晓东编著，电子工业出版社）。我对代码做了少许修改，使可以在tc的图形模式下看到题目的结果。

题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。现在要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），切任何两个L型方块不能重叠覆盖。L型方块的形态如下：

■■*■■***■*■
■******■*■■*■■

题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，知道子棋盘的大小为1为止。
用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法。

Answer 2

看看