问题

一个 的棋盘里有一个格子为特殊方格，现使用占3个格子的L型骨牌（方向任意）填满除特殊方格外的所有格子，问填满一个 的方格需要多少个L型骨牌？

分治策略

试验得知摆放的策略为：将整体的棋盘四等分为4个块，将L型骨牌摆放至四等分的交界处，缺口对应着含有特殊方块的那一个大块，以此规律细分下去就能填满方块（见图）。

1.png

被填上的格子（L骨牌占的格子）又会被作为新的“特殊方块”进行接下来的：分成四块，填没有特殊格的三个方块，分成四块，填方块...

因此可以得到分治与递归的策略如下：

2.png

• 为什么会固定填充？
  • 如果不在某块里，它必定与其他两块一起被一个小L骨牌覆盖。不论特殊方块在哪个大块里，其余的大块的填充位置都集中在中心，可以唯一确定
• “作为一整块”递归的问题：如何递归传递块的位置参数？

  • 可以选择块的左上角的坐标为定位点，传入最开始的左上角坐标作为定位点 ，传入整块的大小 。分割后块的长宽变为 。通过 的运算来找到点的位置，如下图所示

  • 3.png

  • 各点坐标如下：

    • 左上角块：起始点 (tr,tc) 填充点 (tr+s-1,tc+s-1)
    • 右上角块：起始点 (tr+s,tc) 填充点 (tr+s,tc+s-1)
    • 左下角块：起始点 (tr,tc+s) 填充点 (tr+s-1,tc+s)
    • 右下角块：起始点 (tr+s,tc+s) 填充点 (tr+s, tc+s)

伪代码

chessBoard(tr, tc, dr, dc, size) # 传入起点坐标 特殊方格坐标 棋盘大小
    if (大小为1)
        return
        
    t = ++tile # 骨牌号
    s = size / 2 # 分隔后的大小
    
    if (特殊点在左上格)
        chessBoard(tr, tc, dr, dc, s) # 起始点不变 特殊点不变
    else # 没在左上格里就填充右下
        board(右下) = t
        chessboard(tr, tc, tr+s-1, tc+s-1, s) # 特殊点坐标为右下角坐标
        
    if (特殊点在右上格)
        chessBoard(tr+s, tc, dr, dc, s) # 起始点改变为右上起始点 特殊点不变
    else # 没在右上格里就填充左下
        board(左下) = t
        chessboard(tr+s, tc, tr+s, tc+s-1, s) # 起始点变右上块起始坐标，特殊点坐标为左下角坐标
        
    if (特殊点在左下格)
        chessBoard(tr, tc+s, dr, dc, s) # 起始点不变 特殊点不变
    else # 没在左下格里就填充右上
        board(右上) = t
        chessboard(tr, tc+s, tr+s-1, tc+s, s) # 特殊点坐标为右上角坐标
        
    if (特殊点在右下格)
        chessBoard(tr+s,tc+s, dr, dc, s) # 起始点右下 特殊点不变
    else # 没在右下格里就填充左上
        board(左上) = t
        chessboard(tr+s, tc+s, tr+s, tc+s, s) # 特殊点坐标为左上角坐标