分治法——棋盤覆蓋問題
棋盤覆蓋問題。有一個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)載請附上博文鏈接！