[分治与递归]棋盘覆盖问题

问题描述

由一个2^k×2k个方格组成的棋盘中，在这种情况下仅存在一个异常方格，则该棋盘被称为异常棋盘。在解决棋盘覆盖问题时，则需采用四种不同形态的L型骨牌来覆盖该异常棋盘除异常方格外的所有方格，并且禁止任意两个L型骨牌相互重叠地覆盖同一区域。

输入：给定k(1<=k<=10)，表示棋盘大小为 2^k×2k ，在给出特殊方格坐标x,y(0<=x,y<=1024)。

Output结果：一个边长等于2的k次幂的矩阵中存在一个特殊单元格标记为0号；所有骨牌起始编号为1；各数据之间以TAB分隔符分隔。

样例输入：2 0 1

样例输出：

2 0 3 3

2 2 1 3

4 1 1 5

4 4 5 5

分析：

解决这个问题的关键是如何划分各个L型骨牌所处的位置区域。通过观察我们发现每个L型骨牌占据三个方格，并且可以将整个棋盘从中央分成四块。那么在这四块子棋盘中仅有一个