分治法求解棋盘覆盖问题C++

棋盘覆盖问题是指用特殊形状的骨牌覆盖给定的矩形棋盘，要求每个骨牌恰好覆盖棋盘上的3个格子，且任何两个骨牌不重叠、不相邻。棋盘覆盖问题可以用分治法求解。

具体思路如下：

1. 将大棋盘划分成四个小棋盘，每个小棋盘的大小是原来棋盘的一半。

2. 如果当前小棋盘是1x1大小，则直接返回，因为无法再分割。

3. 在当前小棋盘中找到一个空缺格子，将其所在的小方块用一个L型骨牌覆盖。

4. 在剩余的小棋盘中递归执行步骤3，直到所有的小方块都被覆盖。

下面是C++代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1<<5;   // 棋盘最大大小
int board[MAXN][MAXN];   // 棋盘
int tile = 1;            // 骨牌编号

// 分治法求解棋盘覆盖问题
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    if(size == 1) return;
    int t = tile++;
    int s = size / 2;

    // 分治左上角的棋盘
    if(dr < tr+s && dc < tc+s) ChessBoard(tr, tc, dr, dc, s);
    else {
        board[tr+s-1][tc+s-1] = t;
        ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
    }

    // 分治右上角的棋盘
    if(dr < tr+s && dc >= tc+s) ChessBoard(tr, tc+s, dr, dc, s);
    else {
        board[tr+s-1][tc+s] = t;
        ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
    }

    // 分治左下角的棋盘
    if(dr >= tr+s && dc < tc+s) ChessBoard(tr+s, tc, dr, dc, s);
    else {
        board[tr+s][tc+s-1] = t;
        ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
    }

    // 分治右下角的棋盘
    if(dr >= tr+s && dc >= tc+s) ChessBoard(tr+s, tc+s, dr, dc, s);
    else {
        board[tr+s][tc+s] = t;
        ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
    }
}

int main()
{
    memset(board, 0, sizeof(board));   // 初始化棋盘
    int k = 3;                          // 棋盘大小
    int dr = 3, dc = 2;                 // 空缺位置
    ChessBoard(0, 0, dr, dc, 1<<k);
    for(int i=0; i<(1<<k); i++) {
        for(int j=0; j<(1<<k); j++) {
            if(board[i][j] == 0) cout << "- ";   // 空格
            else cout << board[i][j] << " ";     // 骨牌编号
        }
        cout << endl;
    }
    return 0;
}

以上代码输出的结果如下：

4 4 1 1 12 12 9 9 
4 4 1 1 12 12 9 9 
11 11 6 2 2 7 8 8 
11 11 6 3 3 7 7 10 
5 5 5 3 13 13 10 - 
5 5 14 14 13 - - - 
15 15 15 14 - - - -