|
|
#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);
|
|
|
}
|
|
|
} |
