分治法——棋盤覆蓋問題
棋盤覆蓋問題。有一個2k?2k2k?2k的方格棋盤，恰有一個方格是黑色的诱告，其他為白色。你的任務(wù)是用包含3個方格的L型牌覆蓋所有白色方格民晒。黑色方格不能被覆蓋精居，且任意一個白色方格不能同時被兩個或更多牌覆蓋。如圖所示為L型牌的4種旋轉(zhuǎn)方式潜必。
分治三步驟
劃分問題：將2k?2k2k?2k的棋盤劃分為2k?1?2k?12k?1?2k?1這樣的子棋盤4塊靴姿。
遞歸求解：遞歸填充各個格子，填充分為四個情況磁滚，在下面會有解釋佛吓，遞歸出口為k=0k=0也就是子棋盤方格數(shù)為1。
合并問題：不需要合并子問題垂攘。
遞歸填充的四種情況
如果黑方塊在左上子棋盤维雇，則遞歸填充左上子棋盤；否則填充左上子棋盤的右下角晒他，將右下角看做黑色方塊吱型，然后遞歸填充左上子棋盤。
如果黑方塊在右上子棋盤陨仅，則遞歸填充右上子棋盤津滞；否則填充右上子棋盤的左下角，將左下角看做黑色方塊灼伤，然后遞歸填充右上子棋盤触徐。
如果黑方塊在左下子棋盤，則遞歸填充左下子棋盤饺蔑；否則填充左下子棋盤的右上角锌介，將右上角看做黑色方塊，然后遞歸填充左下子棋盤。
如果黑方塊在右下子棋盤孔祸，則遞歸填充右下子棋盤隆敢；否則填充右下子棋盤的右下角，將左上角看做黑色方塊崔慧，然后遞歸填充右下子棋盤拂蝎。
棋盤覆蓋問題分治算法
void chessBoard(int row, int column, int x, int y, int siz) {
// 遞歸出口
if(siz == 1) {
return;
}
// 對半劃分成2^(siz - 1) * 2^(siz - 1)的棋盤
int s = siz / 2;
// L型牌編號自增
int t = ++number;
// 中間點，以此判別(x,y)在哪個子棋盤中
int centerRow = row + s;
int centerColumn = column + s;
// 黑色方格在左上子棋盤
if(x < centerRow && y < centerColumn) {
chessBoard(row, column, x, y, s);
} else {
// 不在則填充左上子棋盤的右下角
chess[centerRow - 1][centerColumn - 1] = t;
// 然后覆蓋其他格子惶室，注意這時(x,y)要看做已填充位置
chessBoard(row, column, centerRow - 1, centerColumn - 1, s);
}
// 黑色方格在右上子棋盤
if(x < centerRow && y >= centerColumn) {
chessBoard(row, centerColumn, x, y, s);
} else {
// 不在則填充右上子棋盤的左下角
chess[centerRow - 1][centerColumn] = t;
// 然后覆蓋其他格子温自，注意這時(x,y)要看做已填充位置
chessBoard(row, centerColumn, centerRow - 1, centerColumn, s);
}
// 黑色方格在左下子棋盤
if(x >= centerRow && y < centerColumn) {
chessBoard(centerRow, column, x, y, s);
} else {
// 不在則填充左下子棋盤的右上角
chess[centerRow][centerColumn - 1] = t;
// 然后覆蓋其他格子，注意這時(x,y)要看做已填充位置
chessBoard(centerRow, column, centerRow, centerColumn - 1, s);
}
// 黑色方格在右下子棋盤
if(x >= centerRow && y >= centerColumn) {
chessBoard(centerRow, centerColumn, x, y, s);
} else {
// 不在則填充右下子棋盤的左上角
chess[centerRow][centerColumn] = t;
// 然后覆蓋其他格子皇钞，注意這時(x,y)要看做已填充位置
chessBoard(centerRow, centerColumn, centerRow, centerColumn, s);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
測試主程序
include <iostream>
using namespace std;
const int maxNum = 1 << 10;
// 棋盤
int chess[maxNum][maxNum];
// L型牌編號
int number;
void chessBoard(int row, int column, int x, int y, int siz) {
// 遞歸出口
if(siz == 1) {
return;
}
// 對半劃分成2^(siz - 1) * 2^(siz - 1)的棋盤
int s = siz / 2;
// L型牌編號自增
int t = ++number;
// 中間點悼泌，以此判別(x,y)在哪個子棋盤中
int centerRow = row + s;
int centerColumn = column + s;
// 黑色方格在左上子棋盤
if(x < centerRow && y < centerColumn) {
chessBoard(row, column, x, y, s);
} else {
// 不在則填充左上子棋盤的右下角
chess[centerRow - 1][centerColumn - 1] = t;
// 然后覆蓋其他格子，注意這時(x,y)要看做已填充位置
chessBoard(row, column, centerRow - 1, centerColumn - 1, s);
}
// 黑色方格在右上子棋盤
if(x < centerRow && y >= centerColumn) {
chessBoard(row, centerColumn, x, y, s);
} else {
// 不在則填充右上子棋盤的左下角
chess[centerRow - 1][centerColumn] = t;
// 然后覆蓋其他格子夹界，注意這時(x,y)要看做已填充位置
chessBoard(row, centerColumn, centerRow - 1, centerColumn, s);
}
// 黑色方格在左下子棋盤
if(x >= centerRow && y < centerColumn) {
chessBoard(centerRow, column, x, y, s);
} else {
// 不在則填充左下子棋盤的右上角
chess[centerRow][centerColumn - 1] = t;
// 然后覆蓋其他格子馆里，注意這時(x,y)要看做已填充位置
chessBoard(centerRow, column, centerRow, centerColumn - 1, s);
}
// 黑色方格在右下子棋盤
if(x >= centerRow && y >= centerColumn) {
chessBoard(centerRow, centerColumn, x, y, s);
} else {
// 不在則填充右下子棋盤的左上角
chess[centerRow][centerColumn] = t;
// 然后覆蓋其他格子，注意這時(x,y)要看做已填充位置
chessBoard(centerRow, centerColumn, centerRow, centerColumn, s);
}
}
int main() {
// 大小可柿，黑色方格位置
int siz, x, y;
while(true) {
cout << "(x,y)從(0,0)開始,輸入數(shù)據(jù)為0 0 0即結(jié)束程序鸠踪。" << endl;
cout << "請輸入棋盤大小和黑色方格位置(x,y)：";
cin >> siz >> x >> y;
// 退出條件
if(siz == 0) {
break;
}
// 涂黑(x,y)，初始化L型牌編號
chess[x][y] = number = 1;
// 分治法填滿棋盤
chessBoard(0, 0, x, y, siz);
// 輸出該棋盤
for(int i = 0; i < siz; i++) {
for(int j = 0; j < siz; j++) {
cout << chess[i][j] << "\t";
}
cout << endl << endl << endl;
}
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
輸出數(shù)據(jù)
(x,y)從(0,0)開始,輸入數(shù)據(jù)為0 0 0即結(jié)束程序复斥。
請輸入棋盤大小和黑色方格位置(x,y)：2 0 0
1 2
2 2
(x,y)從(0,0)開始,輸入數(shù)據(jù)為0 0 0即結(jié)束程序营密。
請輸入棋盤大小和黑色方格位置(x,y)：4 1 1
3 3 4 4
3 1 2 4
5 2 2 6
5 5 6 6
(x,y)從(0,0)開始,輸入數(shù)據(jù)為0 0 0即結(jié)束程序。
請輸入棋盤大小和黑色方格位置(x,y)：8 2 2
4 4 5 5 9 9 10 10
4 3 3 5 9 8 8 10
6 3 1 7 11 11 8 12
6 6 7 7 2 11 12 12
14 14 15 2 2 19 20 20
14 13 15 15 19 19 18 20
16 13 13 17 21 18 18 22
16 16 17 17 21 21 22 22
(x,y)從(0,0)開始,輸入數(shù)據(jù)為0 0 0即結(jié)束程序目锭。
請輸入棋盤大小和黑色方格位置(x,y)：0 0 0
Process returned 0 (0x0) execution time : 29.988 s
Press any key to continue.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
作者：Switch_vov
來源：CSDN
原文：https://blog.csdn.net/q547550831/article/details/51541527
版權(quán)聲明：本文為博主原創(chuàng)文章评汰，轉(zhuǎn)載請附上博文鏈接！
