#include <bits/stdc++.h>

using namespace std;

// [C++] 分治法之棋盘覆盖
// https://www.cnblogs.com/crx234/p/5988055.html

int num = 0;
int cb[100][100];

//函数先声明，后使用
void chessBoard(int tr, int tc, int dr, int dc, int size);

int main() {
    //输入+输出重定向
    freopen("../FenZhi/QiPanFuGai.txt", "r", stdin);

    int size, r, c, row, col;
    cout << "请输入正方形棋盘的大小（行数）:" << endl;
    cin >> size;

    cout << "请输入棋盘上不可覆盖点的位置:" << endl;
    cin >> row >> col;

    printf("不可覆盖点位置输入完毕，不可覆盖点的值为-1\n");
    cb[row][col]=-1;

    //调用主函数
    chessBoard(0, 0, row, col, size);

    //输出结果
    for (r = 0; r < size; r++) { //行
        for (c = 0; c < size; c++) { //列
            printf("%2d ", cb[r][c]);
        }
        cout << endl;
    }

    //关闭文件
    fclose(stdin);
    return 0;
}

/**
 * 功能：棋盘覆盖的递归实现代码
 * @param tr 棋盘左上角方格的行号
 * @param tc 棋盘左上角方格的列号
 * @param dr 特殊方格所在的行号
 * @param dc 特殊方格所在的列号
 * @param size 棋盘的规格（size * size)
 */
void chessBoard(int tr, int tc, int dr, int dc, int size) {
    int s, t;
    if (size == 1) return;  //递归出口,也就是到达了特殊方格框
    s = size / 2;           //变量s来记录边的方格数,每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。
    t = ++num;              //L型骨牌号,从1开始,1,2,3,4,5,...

    //如果不可覆盖点在左上角，就对这个棋盘左上角的四分之一重新进行棋盘覆盖
    if (dr < tr + s && dc < tc + s) {
        chessBoard(tr, tc, dr, dc, s);
    } else {
        //因为不可覆盖点不在左上角，所以我们要在右下角构造一个不可覆盖点
        cb[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 {  //因为不可覆盖点不在右上角，所以我们要在左下角构造一个不可覆盖点
        cb[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 {
        cb[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 {
        //因为不可覆盖点不在右下角，所以我们要在左上角构造一个不可覆盖点
        cb[tr + s][tc + s] = t;
        //在我们构造完不可覆盖点之后，棋盘的右下角的四分之一又有了不可覆盖点，所以就对右下角棋盘的四分之一进行棋盘覆盖
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}