分治法高效求解Tile贴L型瓷砖问题

高效求解Tile贴L型瓷砖问题"/>

分治法高效求解Tile贴L型瓷砖问题

2.1.3 TileBoard 

        TileBoard是一种通过分治思想对平面进行分割，对一个N*N的格子的平面贴上L型瓷砖的算法，注意N为2的幂数，其中有一个空缺基本方格是不需要贴的，L型瓷砖是3个基本方格组成的。

       为什么这个问题可用分治法呢？假设N=8，那么就有64个基本方格，那么如果随意贴L型瓷砖，你会发现最后贴不下去，最后剩下3个基本方格没有连在一起，其实就是拼图原理。那么一种贴图的方式，让最后的平面铺满L型瓷砖，除了空缺基本方格。这也刚好符合3m+1=N*N的数学原理，即N为2的幂数。

      分治法的数学理论本质上是归纳法的逆推证明：分治法——由大及小；归纳法——由小及大。

1. 对于基本问题，当n==2时，就是含有4个基本方格的平面，很显然直接贴一个L型瓷砖即可。
2. 当n=2k时，如果能分解成t=n/4个含有4个基本方格的平面；论证：16基本方格从中间轴分解成4个大小相同包含4个基本方格的平面；而如果是64个则可以分为4个含有16个基本方格的平面，同理类推；而2k*2k=4k个基本方格，所以最终会含有4k-1个含有4个基本方格的平面。
3. 如果n=2k时成立，即(n*n)/4==22k-2个小平面，则当n=2k+1时，则包含22k个小平面，即可以分为包含4个基本方格的平面，得证。为什么这样就得证了呢？因为前提是含有2的幂次的小方格，如果是4*5个小方格就无法分成包含4个基本方格大小相同的平面。而22k-2和22k都是4的幂数，可以分，所以论证成立。

         如何通过代码实现上面的想法呢？

        这里是采用先分后治还是先治后分呢，其实是根据在分的时候是否是依据治的结果来分的，就行快速排序，它的分是依据治的结果来左右分的，所以是先治后分；而合并排序则是先将大的数分成少的数，然后进行治，所以是先分后治。而TileBoard 则是依据治的结果来调用递归分的函数，所以是先治后分。（特注：是先治后分还是先分后治不是根据递归函数程序是否放在治的前面或者后面面来决定的，因为分函数放在前面还是后面其实都可以，根据判断终结递归的if等条件，可以将分写在前或者后都是一样的；而是分和治关系的依据是依据治的结果来决定的。

那么，可以先实现一个分治法的基本框架：

//tile problem
void DivideMerge::Tile(int sum, Point point, Point position)
{//基本递归框架，即在满足什么条件时，继续调用函数，这里的函数不限制,一分四     ,所有的坐标全是右下角的坐标//point.setTile(true);if (sqrt(sum) >2){int len = sqrt(sum); int t = len / 2;Point leftUpPosition, leftDownPosition, rightUpPosition, rightDownPosition;Point centerPoint;centerPoint.setX(position.getX() - t);centerPoint.setY(position.getY() - t);leftUpPosition.setX(position.getX() - t);leftUpPosition.setY(position.getY() - t);leftDownPosition.setX(position.getX());leftDownPosition.setY(position.getY()-t);rightUpPosition.setX(position.getX()-t);rightUpPosition.setY(position.getY());rightDownPosition.setX(position.getX());rightDownPosition.setY(position.getY());//****************************************************************Point leftUpPoint, leftDownPoint, rightUpPoint, rightDownPoint;              //这里是空点或者已贴tile的点//直接计算以上这些点的位置坐标，并将其tile改为true,可以将最初的空的看作为true???//point 是空缺位置或者已填充位置//point 是当前的空缺位置 ，注意当光标变宽时，按下insert键恢复int quadrant;           //分别用象限来表示空缺点和填充点的位置if (point.getX() <= centerPoint.getX() ){if (point.getY() <= centerPoint.getY()){quadrant = 2;                      //空缺位在第二象限}else{quadrant = 1;}}else{if (point.getY() <= centerPoint.getY()){quadrant = 3;                      //空缺位在第二象限}else{quadrant = 4;}}switch (quadrant){case 1:{//说明point在第一象限rightUpPoint = point;leftUpPoint.setTile(true);leftUpPoint.setX(centerPoint.getX());leftUpPoint.setY(centerPoint.getY());leftDownPoint.setTile(true);             //第三象限leftDownPoint.setX(centerPoint.getX()+1);leftDownPoint.setY(centerPoint.getY());rightDownPoint.setTile(true);rightDownPoint.setX(centerPoint.getX() + 1); //第四象限rightDownPoint.setY(centerPoint.getY() + 1);}break;case 2:{//说明point在第二象限leftUpPoint = point;leftDownPoint.setTile(true);                     //第三象限leftDownPoint.setX(centerPoint.getX()+1);leftDownPoint.setY(centerPoint.getY());rightUpPoint.setTile(true);                      //第一象限rightUpPoint.setX(centerPoint.getX());rightUpPoint.setY(centerPoint.getY()+1);rightDownPoint.setTile(true);rightDownPoint.setX(centerPoint.getX() + 1);      //第四象限rightDownPoint.setY(centerPoint.getY() + 1);}break;case 3:{leftDownPoint = point;leftUpPoint.setTile(true);leftUpPoint.setX(centerPoint.getX());leftUpPoint.setY(centerPoint.getY());rightUpPoint.setTile(true);              //第一象限rightUpPoint.setX(centerPoint.getX());rightUpPoint.setY(centerPoint.getY()+1);rightDownPoint.setTile(true);rightDownPoint.setX(centerPoint.getX() + 1); //第四象限rightDownPoint.setY(centerPoint.getY() + 1);}break;case 4:{rightDownPoint = point;leftUpPoint.setTile(true);leftUpPoint.setX(centerPoint.getX());leftUpPoint.setY(centerPoint.getY());leftDownPoint.setTile(true);leftDownPoint.setX(centerPoint.getX() + 1); //第3象限leftDownPoint.setY(centerPoint.getY());rightUpPoint.setTile(true);              //第一象限rightUpPoint.setX(centerPoint.getX());rightUpPoint.setY(centerPoint.getY() + 1);}break;}Tile(sum / 4, leftUpPoint, leftUpPosition);                     //左上Tile(sum / 4, leftDownPoint, leftDownPosition);                     //左下Tile(sum / 4, rightUpPoint, rightUpPosition);                     //右上Tile(sum / 4, rightDownPoint, rightDownPosition);                     //右下}else if(sqrt(sum)==2)                                                          //if(sqrt(n)==2),说明只存在一个位置可以tile{//直接将未tile的点tile//position肯定是右下角，而point则是空点或者已填充点//将剩下的最后4个全部填充quardPoint[point.getX()][point.getY()] = point;}//else if
}

       总结：Tile算法算法的实现主要是对基本方格的存储，程序中采用point类来存储，其中包含x,y的位置坐标和标志位，即标记已经贴了L型瓷砖的方格位true。其中x,y与数组的下标相对应。

       而治的方法：如果空缺或者已贴的小方格在已分成的4个平面的左上平面，则对其余的3个平面中与左上平面右下角相邻的小方格贴一个L型瓷砖，即将周围的3个小方格point的标志位设置为true。

     该程序的算法逻辑不难，主要是对数据进行存储，数据善置，算法自成。

    下面是主调函数：

vector<vector<Point>> DivideMerge::TileBoard(int n, int m, Point point)            //point为初始空缺点
{//可以用一个,点值初始化quardPoint.resize(n+1);for (int i = 0; i <= n; i++){quardPoint[i].resize(m+1);}for (int i = 0; i <= n; i++){for (int j = 0; j <= m; j++){quardPoint[i][j] = *new Point();quardPoint[i][j].setTile(false);quardPoint[i][j].setX(i);quardPoint[i][j].setY(j);}}Point position;position.setX(n);position.setY(m);                           //右下角的顶点坐标int sum = n*m;Tile(sum, point, position);               //调用递归函数  Tile(int n, Point point, Point position)quardPoint[point.getX()][point.getY()].setTile(false);return quardPoint;
}