信息学竞赛辅导 残缺棋盘问题——分治法

 /* 残缺棋盘

    
 一个有2k×2k个方格的棋盘，其中恰有一个方格残缺。
    
   4. 在残缺棋盘问题中，要求用三格板（triominoes）覆盖残缺棋盘。
    
 在此覆盖中，两个三格板不能重叠。三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。
    
 在这种限制条件下，所需要的三格板总数为(22k-1)/3 ，可以验证(22k-1)/3是一个整数。
    
   8. 2k×2k棋盘一个很自然的划分方法就是将它划分为4个2k-1×2k-1棋盘。
    
 注意到当完成这种划分后，4个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的棋盘仅仅有一个残缺方格）。
    
 　　对原2k×2k残缺棋盘的覆盖按如下两个步骤可以转化为对2k-1×2k-1残缺棋盘的覆盖：
    
 　　第一步，覆盖其中包含残缺方格的2k-1×2k-1残缺棋盘；
    
 　　第二步：将一个三格板放在由剩下的3个小棋盘形成的角上，从而把这3个小棋盘转变为2k-1×2k-1 残缺棋盘，
    
 		其中原2k×2k棋盘中的残缺方格落入左上角的2k-1×2k-1小棋盘中。
    
 		采用这种分割技术可以递归地覆盖2k×2k 残缺棋盘。当棋盘的大小减为1×1时，递归过程终止。
    
 		此时1×1的棋盘中仅仅包含一个方格且此方格残缺，所以无需放置三格板。