棋盘覆盖

【问题描述】在一个2k×2k 方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。现在要用以下4种不同形态的L形骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。求一种覆盖方法。

4种L形骨牌特殊棋盘，不能把骨牌放在黑色方格上面。

【分析】尺寸为2k×2k，我们可以想到将其分割成四个尺寸为2k-1×2k-1的子棋盘。

接下来，将L型放置在棋盘的正中央，使四个子棋盘都变成特殊棋盘（一个子棋盘含有特殊方格，另外三个子棋盘恰好被骨牌覆盖，如下图）。此时问题也变成了四个相同的子问题，只需简单地对四小块区域进行递归，就可以解决这道问题了。

“L”型骨牌

代码的时间复杂度和空间复杂度都是O(4k)。由于覆盖一个2k×2k 棋盘所需的L型骨牌个数为(4k－1)/3，所以算法已经是最优的了。