棋盘覆盖问题 C++实现11

到底出处是哪里？是谁抄谁的还是都是抄别人的，那就不得而知了。

本博客不会这样照搬复述的，本博客的文章都是自己的理解总结出来，和自己思考所得的结论，最多包含某些书本的精要概括，绝对原创，要引用本博客内容的朋友请注明出处。

这里就指出重点和难点加以分析。并改正其错误。

这里就不复述问题了，简单来说就是利用L型的骨牌，填充2^k*2^k的方形棋盘。其中棋盘用2维数组表示，这里用vector > board表示。

解决这个问题的方法也是分治法，需要用到递归，重点难点如下：

1. 递归问题的思考应该从最小问题开始，比如这道题就应该从a[2][2]这个最小规模的问题思考起来，然后当数组更加大的时候，情况也是一样的。大家可以看做这个是思考的突破口！如果实在难以理解，只能是用[4][[4]这样大一点的棋盘，画图，然后一步一步，一个递归一个递归层地区手动走一走程序了。之所以难理解是因为它有四个分支递归，因为分了四个区域。

2. 这道题的填充的是由3个格组成的L型骨牌，注意的就是这个骨牌要想象成为是可以拆分成3个格分别填充的。只要最后组成了一个一个完整的L型骨牌就算符合要求了。

勘误：主要是填的骨牌序号问题，那个需要用一个stack来保存，才能保证所填的序号无误。一般书上都不用栈，会导致填充不正确。

其他的且看程序详细注解：

#include  
#include  
#include  
  
using namespace std;  
  
vector > board(4);//棋盘数组，也可以作为参数传递进chessBoard中去，作为全局变量可以减少参数传递  
stack stI;   //记录当前所使用的骨牌号码，使用栈顶元素填充棋盘数组  
int sL = 0;     //L型骨牌序号  
  
//所有下标皆为0开始的C C++下标  
void chessBoard(int uRow, int lCol, int specPosR, int specPosC, int rowSize)  
{  
    if(rowSize ==1) return;  
    //static int sL = 0;棋牌和骨牌都可以用static代替，如果不喜欢用全局变量的话。  
    sL++;     
    stI.push(sL); //每递归深入一层，就把一个骨牌序号入栈  
    int halfSize = rowSize/2;//拆分  
  
    //注意：下面四个if else，肯定是只有一个if成立，然后执行if句，而肯定有三个else语句要执行的，因为肯定有一个是特殊位置，而其他三个是空白位置，需要填充骨牌。  
  
    //1如果特殊位置在左上角区域，则继续递归，直到剩下一个格子，并且该格子已经填充，遇到函数头一句if(rowSize == 1) return;就跳出一层递归。  
    //注意是一个区域或子棋盘，有一个或者多个格子，并不是就指一个格子。  
    if(specPosR





=lCol+halfSize)  
        chessBoard(uRow, lCol+halfSize, specPosR, specPosC, halfSize);  
    else  
    {  
        board[uRow+halfSize-1][lCol+halfSize] = stI.top();  
        chessBoard(uRow, lCol+halfSize, uRow+halfSize-1, lCol+halfSize, halfSize);  
    }         
  
    //3左下角区域，类上  
    if(specPosR>=uRow+halfSize && specPosC=uRow+halfSize && specPosC>=lCol+halfSize)  
        chessBoard(uRow+halfSize, lCol+halfSize, specPosR, specPosC, halfSize);  
    else  
    {  
        board[uRow+halfSize][lCol+halfSize] = stI.top();  
        chessBoard(uRow+halfSize, lCol+halfSize, uRow+halfSize, lCol+halfSize, halfSize);  
    }     
  
    stI.pop();//本次骨牌号填充了三个格，填充完就出栈  
}  
  
void test()  
{  
    //初始化数组  
    for(int i=0; i<4; i++)  
    {  
        board[i].resize(4);  
    }  
  
    chessBoard(0, 0, 3, 3, 4);  
  
    //特殊位置填充0  
    board[3][3] = 0;  
  
    //序列输出  
    for(int j=0; j<4; j++)  
    {  
        for(int i=0; i<4; i++)  
            cout< 
  
 
 
 

总结：

递归法的确很难，分治法应用递归就更加难了。思路要清晰，具体例子分析一下。