分治法之棋盘覆盖复牌问题,c++实现
问题描述
一个棋盘,其中有一个特殊点,用L的骨牌去覆盖,骨牌不能重叠,如何做到全部覆盖,如图:
![在这里插入图片描述](https://img-blog.csdnimg.cn/3ba0eedd2e5944c1bbd6947513fed6f9.png)
实现
- 采用分治法
- 将一个棋盘划分为4个棋盘,有一个棋盘存在特殊点,其他三个棋盘没有特殊点
- 将没有特殊点的棋盘连接,用L型骨牌连接三个棋盘,使每个棋盘变成有一个特殊点的子棋盘
- 重复操作,直到大小为1,算法结束
// 将一个棋盘划分为4个棋盘,则有三个棋盘是没有特殊点的,将这三个棋盘用一个L型骨牌连接,将会得到一个规模小的子棋盘
// # 假设特殊点的下标为dr,dc,棋盘左上角坐标为tr,tc,大小为s
// # 初始化,dr = 1,dc = 1;tr = 0;tc = 0;s = 8;
// # 棋盘用board[size][size]二维数组表示,size = 2^k
#include
using namespace std;
const int n = 8;
int t = 1;
int board[n][n] = {0};
void chessBoard(int tr, int tc, int dr, int dc, int size) {
if (size == 1) return;
int t1 = ++t;
// 牌号+1
int s = size / 2;
// 划分棋盘为4块
// 分别针对特殊点的位置对棋盘进行递归
// 特殊点在左上角, tr+s表示左上角棋盘的范围
// 1. 左上角棋盘处理
if (dr < tr + s && dc < tc + s) {
chessBoard(tr, tc, dr, dc, s);
// 直接递归
} else {
board[tr+s-1][tc+s-1] = t1;
// 特殊点
chessBoard(tr, tc, tr+s-1, tc+s-1, s);
// 左上角的棋盘特殊标记放在右下角
}
// 2. 右上角棋盘处理
if (dr < tr + s && dc >= tc + s) {
chessBoard(tr, tc+s, dr, dc, s);
// 直接递归
} else {
board[tr+s-1][tc+s] = t1;
// 特殊点
chessBoard(tr, tc+s, tr+s-1, tc+s, s);
// 右上角的棋盘特殊标记放在左下角
}
// 3. 左下角棋盘处理
if (dr >= tr + s && dc < tc + s) {
chessBoard(tr+s, tc, dr, dc, s);
// 直接递归
} else {
board[tr+s][tc+s-1] = t1;
// 特殊点
chessBoard(tr+s, tc, tr+s, tc+s-1, s);
// 左下角的棋盘特殊标记放在右上角
}
// 4. 左上角棋盘处理
if (dr >= tr + s && dc >= tc + s) {
chessBoard(tr+s, tc+s, dr, dc, s);
// 直接递归
} else {
board[tr+s][tc+s] = t1;
// 特殊点
chessBoard(tr+s, tc+s, tr+s, tc+s, s);
// 左上角的棋盘特殊标记放在右下角
}
}int main() {
board[1][1] = t;
chessBoard(0, 0, 1, 1, n);
for (int i = 0;
i < n;
i++) {
for (int j = 0;
j < n;
j++) {
cout<< board[i][j] << "\t";
}
cout<
【分治法之棋盘覆盖复牌问题,c++实现】
文章图片
如图,数字代表覆盖顺序