棋盤覆寫問題算法分析與實作（遞歸）

*昨天上傳的代碼，經過再次測試發現有問題，其中對邊界、終止條件的判斷都有錯誤。。。→_→，今天重新改正，對之前看過代碼的童鞋表示sorry。。。（2017.5.13 16：24）*

問題描述：

在一個2^k×2^k （k≥0）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為特殊方格。顯然，特殊方格在棋盤中可能出現的位置有4^k種，因而有4^k種不同的棋盤。棋盤覆寫問題（chess cover problem）要求使用4種不同形狀的L型骨牌覆寫給定棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆寫。

關于棋盤劃分的更多概念請戳傳送門：棋盤覆寫問題

實作如下：

class Solution
{
public:
    int num = ;//累計計算
    int **board = NULL;//動态二維數組指針
    void printBoard(int **board, int row, int col)//輸出函數
    {
        for (int i = ; i < row; ++i)
        {
            for (int j = ; j < col; ++j)
                cout << setw() <<board[i][j];
            cout << endl;
        }
        cout << endl;
    }

    void createBoard(int chessboardSize, int dr, int dc)//動态申請記憶體函數
    {
        board = (int **)malloc(chessboardSize * sizeof(int*));
        assert(board != NULL);
        for (int i = ; i < chessboardSize; ++i)
        {
            board[i] = (int*)malloc(chessboardSize * sizeof(int));
            assert(board[i] != NULL);
            memset(board[i], , sizeof(int)*chessboardSize);
        }
        board[dr][dc] = -;//将特殊點設定為-1
    }

    void freeBoard(int row)//釋放動态記憶體空間，防止記憶體洩漏
    {
        for (int i = ; i < row; ++i)
            free(board[i]);
        free(board);
    }
    //chessboardSize表示此時範圍的n*n，n的值
    //dr表示特殊點的行下标
    //dc表示特殊點的列下标
    //tr表示此時範圍的左上角在數組中的行下标
    //tc表示此時範圍的左上角在數組中的列下标
    void Coverage(int chessboardSize, int dr, int dc, int tr, int tc)
    {
        if (chessboardSize == ) return;//當範圍為1時，表示隻有一個元素，return
        int tmp = ++num;//每進入一個範圍内，num累加
        int s = chessboardSize / ;//擷取此時範圍内的下一個小範圍的n大小
        //判斷特殊點是否在範圍内的第一象限
        if (dr < tr + s && dr >=  && dc < tc + s && dc >= )
                    Coverage(s, dr, dc, tr, tc);
        else//否則，将此第一象限的右下角設定為相對特殊點
        {
            board[tr + s - ][tc + s - ] = tmp;
            Coverage(s, tr + s - , tc + s - , tr, tc);
        }
        //判斷特殊點是否在範圍内的第四象限
        if (dr >=  && dr < tr + s && dc >= tc + s && dc < tc +  * s)
            Coverage(s, dr, dc, tr, tc + s);
        else//否則，将此第四象限的右下角設定為相對特殊點
        {
            board[tr + s - ][tc + s] = tmp;
            Coverage(s, tr + s - , tc + s, tr, tc + s);
        }
        //判斷特殊點是否在範圍内的第二象限
        if (dr >= tr + s && dr < tr +  * s && dc >=  && dc < tc + s)
            Coverage(s, dr, dc, tr + s, tc);
        else//否則，将此第二象限的右下角設定為相對特殊點
        {
            board[tr + s][tc + s - ] = tmp;
            Coverage(s, tr + s, tc + s - , tr + s, tc);
        }
        //判斷特殊點是否在範圍内的第三象限
        if (dr >= tr + s && dr < tr +  * s && dc >= tc + s && dc < tc +  * s)
            Coverage(s, dr, dc, tr + s, tc + s);
        else//否則，将此第三象限的右下角設定為相對特殊點
        {
            board[tr + s][tc + s] = tmp;
            Coverage(s, tr + s, tc + s, tr + s, tc + s);
        }
        //printBoard(board, 8, 8);
    }

    void ChessboardCoverage(int chessboardSize, int dr, int dc)
    {
        if (chessboardSize <  || dr <  || dc <  || dr >= chessboardSize || dc >= chessboardSize) return;//防禦性動作
        createBoard(chessboardSize, dr, dc);//動态生成二維數組
        Coverage(chessboardSize, dr, dc, , );//開始覆寫
        printBoard(board, chessboardSize, chessboardSize);//輸出
        freeBoard(chessboardSize);//釋放動态空間
    }
};
           

測試用例：