使用分治法解决棋盘覆盖c/c++

棋盘覆盖问题是指在一个2^n * 2^n的棋盘上，恰好有一个方格与其他方格不同，要用L型骨牌（由3个方格组成，其中一个是“凸”出来的）将这个方格覆盖住。可以使用分治法来解决这个问题。

具体步骤如下：
1. 如果棋盘的大小为1 * 1，则直接用一个L型骨牌覆盖即可。
2. 将棋盘分成四个大小相等的子棋盘，分别记为A、B、C、D。设需要覆盖的特殊方格在子棋盘A中，用一个L型骨牌覆盖这个特殊方格。然后，将剩下的三个小棋盘中的特殊方格分别用三个L型骨牌覆盖，这三个L型骨牌的凸出方向均与第一个L型骨牌不同。
3. 对于子棋盘A、B、C、D，分别递归执行步骤2，直到棋盘大小为1 * 1为止。

下面是C/C++代码实现：

#include <stdio.h>

#define MAX_N 1024

int board[MAX_N][MAX_N];
int tile = 1;

// r, c: 特殊方格的位置
// tr, tc: 棋盘左上角的位置
void solve(int size, int tr, int tc, int r, int c) {
    if (size == 1) return;

    int t = tile++;
    int s = size / 2;

    // 覆盖左上角子棋盘
    if (r < tr + s && c < tc + s) {
        solve(s, tr, tc, r, c);
    } else {
        board[tr + s - 1][tc + s - 1] = t;
        solve(s, tr, tc, tr + s - 1, tc + s - 1);
    }

    // 覆盖右上角子棋盘
    if (r < tr + s && c >= tc + s) {
        solve(s, tr, tc + s, r, c - s);
    } else {
        board[tr + s - 1][tc + s] = t;
        solve(s, tr, tc + s, tr + s - 1, tc + s);
    }

    // 覆盖左下角子棋盘
    if (r >= tr + s && c < tc + s) {
        solve(s, tr + s, tc, r - s, c);
    } else {
        board[tr + s][tc + s - 1] = t;
        solve(s, tr + s, tc, tr + s, tc + s - 1);
    }

    // 覆盖右下角子棋盘
    if (r >= tr + s && c >= tc + s) {
        solve(s, tr + s, tc + s, r - s, c - s);
    } else {
        board[tr + s][tc + s] = t;
        solve(s, tr + s, tc + s, tr + s, tc + s);
    }
}

int main() {
    int n, r, c;
    scanf("%d %d %d", &n, &r, &c);

    solve(1 << n, 0, 0, r, c);

    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < (1 << n); j++) {
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

其中，`solve()`函数是用于递归解决子问题的。`tile`表示当前骨牌的编号，`s`表示当前棋盘的大小。`tr`和`tc`表示当前棋盘的左上角位置。`r`和`c`表示需要覆盖的特殊方格的位置。`board`数组用于记录骨牌的编号。