(三)棋盘覆盖问题(思路)

一)问题描述:
在一个有2k*2k的正方形方格中,有个一特殊的方格被涂为黑色,现有四种不同形态的L型骨牌覆盖上述除了黑格以外的其余方格,用到的L型骨牌的数量为:(4k-1)/3。
例如:8x8的表格(PPT制图)(三)棋盘覆盖问题(思路)
接下来使用L型骨牌将这个图中剩余部分填满:

(三)棋盘覆盖问题(思路)
填充后的样子:注:相同颜色表示使用了相同的L型骨牌,格子里面的数字表示填图的顺序。这里遵循的规则是:左上,右上,左下,右下的规则

(三)棋盘覆盖问题(思路)
二)程序实现:
代码实现

三)时间复杂度:
T(k)=O(4k)

四)代码实现的结果为:

(三)棋盘覆盖问题(思路)
或者:
(三)棋盘覆盖问题(思路)