(三)棋盘覆盖问题(思路)
一)问题描述:
在一个有2k*2k的正方形方格中,有个一特殊的方格被涂为黑色,现有四种不同形态的L型骨牌覆盖上述除了黑格以外的其余方格,用到的L型骨牌的数量为:(4k-1)/3。
例如:8x8的表格(PPT制图)
接下来使用L型骨牌将这个图中剩余部分填满:
填充后的样子:注:相同颜色表示使用了相同的L型骨牌,格子里面的数字表示填图的顺序。这里遵循的规则是:左上,右上,左下,右下的规则
二)程序实现:
代码实现
三)时间复杂度:
T(k)=O(4k)
四)代码实现的结果为:
或者: