NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 28 题

完善程序： （棋盘覆盖问题）在一个 $2^k\times 2^k$ 个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为 $-1$ 的方格），称之为特殊方格。现 L 型（占 $3$ 个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是 $\dfrac{(4^k-1)}{3}$。在下表给出的一个覆盖方案中，$k=2$，相同的 $3$ 各数字构成一个纸片。下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。

2  2  3  3
2 -1  1  3
4  1  1  5
4  4  5  5

#include <iostream.h>
#include <iomanip.h>
int board[65][65], tile; /* tile为纸片编号 */
void chessboard( int tr, int tc, int dr, int dc, int size )
/* dr,dc依次为特殊方格的行、列号 */
{
	int t, s;
	if ( size == 1 )
		① ;
		t = tile++;
	s = size / 2;
	if ( ② )
		chessboard( tr, tc, dr, dc, s );
	else{
		board[tr + s -1][tc + s -1] = t;
		[③];
	}
	if ( dr < tr + s && dc >= tc + s )
		chessboard( tr, tc + s, dr, dc, s );
	else{
		board[tr + s -1][tc + s] = t;
		④;
	}
	if ( dr >= tr + s && dc < tc + s )
		chessboard( tr + s, tc, dr, dc, s );
	else{
		board[tr + s][tc + s -1] = t;
		[⑤];
	}
	if (

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考分治里的棋盘覆盖。拿到题先想：棋盘太大没法一次铺，必须切半。代码里size==1直接return是终止条件；中间那块t型骨牌放好后，剩下的三个子棋盘各缺一个“特殊格”，得把那个位置填上t再递归进去，这就是填空的核心逻辑。

最容易栽跟头的是坐标判断和伪特殊格的位置。很多同学把dr<tr+s&&dc<tc+s写成dr<tr+s&&dc<tc+s，虽然看着像，但逻辑上是先判断行再判断列，顺序错了会导致进入错误的分支。另外，伪特殊格的坐标容易搞混，比如右上子棋盘的特殊格应该是(tr+s-1, tc+s)，别写成(tr+s, tc+s)或者漏掉一个s。还有递归调用时参数顺序别乱，tr、tc、dr、dc四个参数对应左上角和特殊格位置，少一个或多一个都会直接报错。

棋盘覆盖：分治法的经典实战

这题考什么

这道题考查的是分治算法中的经典模型——棋盘覆盖问题。具体来说，就是如何把一个 $2^k \times 2^k$ 的棋盘（其中恰有一个特殊方格）用 L 型骨牌（覆盖 3 个格子）完全铺满。命题人特别喜欢考这种“看似复杂，实则递归套递归”的题目，因为它能很好地考察学生对递归边界、坐标变换以及分治策略的理解。在初赛里，这类题往往就是填空题，让你补全代码里的关键逻辑。