题目:在一个(2^k)*(2^k)个方格组成的棋盘上,有一个特殊方格与其他方格不同,称为特殊方格,称这样的棋盘为一个特殊棋盘。现在要求对棋盘的其余部分用L型方块填满(注:L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角,方向随意),切任何两个L型方块不能重叠覆盖。L型方块的形态如下:
■■*■■***■*■
■******■*■■*■■
题目的解法使用分治法,即子问题和整体问题具有相同的形式。我们对棋盘做一个分割,切割一次后的棋盘如图1所示,我们可以看到棋盘被切成4个一样大小的子棋盘,特殊方块必定位于四个子棋盘中的一个。假设如图1所示,特殊方格位于右上角,我们把一个L型方块(灰色填充)放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”,我们对每个子棋盘继续这样分割,知道子棋盘的大小为1为止。
用到的L型方块需要(4^k-1)/3 个,算法的时间是O(4^k),是渐进最优解法。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)