分治策略求解棋盘覆盖问题

在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为特殊方格，且称该棋盘为特殊棋盘。试用4种不同形态的L型骨牌, 覆盖给定特殊棋盘上除特殊方格以外的所有方格，且任何2个不得重叠。

1
#include <iostream>
2
using namespace std;
3
4
int CHESS[101][101]={0}; // 最大棋盘数组，行列序号为1～100
5
static int t=0, m; // 临时变量，实际棋盘大小
6
7
// 显示棋盘
8
void show(int length) {
9
    for(int i=1; i<=length; i++)
10
        for(int j=1; j<=length; j++) {
11
            cout.width(3);
12
            cout << CHESS[i][j];
13
            if(j == length)
14
                cout << endl;
15
        }
16
    cout << endl;
17
}
18
19
// 棋盘覆盖算法
20
// 参数：a，b为子棋盘左上角坐标。x，y为特殊点坐标，length为子棋盘长度
21
void chess(int a,int b,int x,int y,int length) {
22
    if(length == 1)
23
        return;
24
    t++;
25
    int tem = t, l = length / 2;
26
27
    if(x<a+l && y<b+l) // 特殊点在左上的正方形中
28
        chess(a,b,x,y,l);
29
    else{
30
        CHESS[a+l-1][b+l-1] = tem;
31
        chess(a, b, a+l-1, b+l-1, l);
32
    }
33
34
    if(x>=a+l && y<b+l) // 左下角的子棋盘
35
        chess(a+l, b, x, y, l);
36
    else{
37
        CHESS[a+l][b+l-1] = tem;
38
        chess(a+l, b, a+l, b+l-1, l);
39
    }
40
41
    if(x<a+l && y>=b+l) // 右上角的子棋盘
42
        chess(a, b+l, x, y, l);
43
    else{
44
        CHESS[a+l-1][b+l] = tem;
45
        chess(a, b+l, a+l-1, b+l, l);
46
    }
47
48
    if(x>=a+l && y>=b+l) // 右下角的子棋盘
49
        chess(a+l, b+l, x, y, l);
50
    else{
51
        CHESS[a+l][b+l] = tem;
52
        chess(a+l, b+l, a+l, b+l, l);
53
    }
54
}
55
56
int main(){
57
    int a, b; // 子棋盘左上角的行号和列号
58
    int x, y; // 特殊点的行号和列号
59
    int length; // 棋盘大小
60
    cout << "请输入棋盘大小（1-100）：";
61
    cin >> length;
62
    cout << "请输入特殊点行号：";
63
    cin >> x;
64
    cout << "请输入特殊点列号：";
65
    cin >> y;
66
    a = b = 1;
67
    chess(a, b, x, y, length);
68
    show(length);
69
    return 0;
70
}