棋盘覆盖问题(chess cover problem)
在\({2^k}\times {2^k}\)的棋盘格(\(k\)为正整数)中,其有1个确定位置的方格一开始是被覆盖的,现提供4种不同L型骨牌(如上图所示)。棋盘覆盖问题要求得到其中1种方案,用这4种骨牌覆盖所有方格,且覆盖是没有任何重叠的。
然后找该问题的分治算法,由于棋盘长宽相等且是2的幂,所以棋盘能拆成等大的4个象限,被覆盖的方格在某个象限里。这时考虑在中心位置选一种形状的骨牌放入1个,要求其刚好横跨另外3个没有被覆盖方格的象限。这时这4个象限每个都刚好有1个被覆盖的方格,这样就可把这4个象限当成“子棋盘”来递归的求解子问题,直到遇到\(2\times 2\)的“子棋盘”时,使用1个骨牌覆盖后就等于完全解决了这个子问题,而无需继续递归下去求更小规模的子问题。
由于问题的输入输出都是“棋盘”,所以用二维数组表示“棋盘”,并直接在这个数组上“覆盖”骨牌。这个程序要避免不必要的遍历,否则会导致时间复杂度变大。然后规定初始覆盖的方格用“X”填充,数组其他位置填“假”,4种骨牌分别填入ABCD的4种字母占位,这样最后打印结果时很清晰。然后构造递归函数\(cover(chess,x_1,x_2,y_1,y_2,x_c,y_c)\),输入1是“棋盘”,输入2-4表示子棋盘坐标的起止位置。输入5-6表示在该子问题中,被覆盖的方格的坐标,下面是具体程序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | """ 象限: 0 --- x | 1 2 | 3 4 y 例子: 0 --- x | O A C C | A A A C y B A A A B B A A """ def cover(chess, x1, y1, x2, y2, xc, yc): # [x1,x2) [y1,y2) if x2 - x1 <= 1: return yMid, xMid = (y1 + y2) // 2, (x1 + x2) // 2 yc1, xc1 = yMid - 1, xMid - 1 yc2, xc2 = yMid - 1, xMid yc3, xc3 = yMid, xMid - 1 yc4, xc4 = yMid, xMid if yc < yMid and xc < xMid: yc1, xc1 = yc, xc chess[yc2][xc2] = "A" chess[yc3][xc3] = "A" chess[yc4][xc4] = "A" elif yc < yMid and xc >= xMid: yc2, xc2 = yc, xc chess[yc1][xc1] = "B" chess[yc3][xc3] = "B" chess[yc4][xc4] = "B" elif yc >= yMid and xc < xMid: yc3, xc3 = yc, xc chess[yc1][xc1] = "C" chess[yc2][xc2] = "C" chess[yc4][xc4] = "C" elif yc >= yMid and xc >= xMid: yc4, xc4 = yc, xc chess[yc1][xc1] = "D" chess[yc2][xc2] = "D" chess[yc3][xc3] = "D" cover(chess, x1, y1, xMid, yMid, xc1, yc1) cover(chess, xMid, y1, x2, yMid, xc2, yc2) cover(chess, x1, yMid, xMid, y2, xc3, yc3) cover(chess, xMid, yMid, x2, y2, xc4, yc4) def solve(level, xc, yc): n = 2**level chess = [ [ None for j in range(n) ] for i in range(n) ] chess[yc][xc] = 'X' cover(chess,0,0,n,n,xc,yc) for i in chess: print(i) solve(2, 3, 2) |
最后分析时间复杂度,实际的问题规模是棋盘格子数\(n\),每个递归包含4个规模\(\frac{1}{4}\)的子递归,除子递归以外的代价只有\(O(1)\),那么时间复杂度\(T(n)\)满足\(T(n)=4T(\frac{n}{4}) + O(1)\)。根据主定理直接得到\(T(n)=O(n)\)。