UVA 10230 Savage Garden

uva recursion

這是個 L-shape 問題, 下面有一個不錯的介紹.
http://tmt514-blog.logdown.com/posts/549466-divide-and-conquer-method-v-l-shaped-brick-problem

解法就是按照上面的連結中２解法的思維去做一次模擬.因為除了迴遞最後一層的 L 形磚都不會有接觸,　所以我把它們都叫 e. 而為了防上顏色會和周邊的一樣,　所以最後一層 L 形磚是根據它的位置決定.

我在迴遞時是畫了正方形, 而不是 L 形. 這是為了令程式比較簡潔. 因為之後的迴遞畫的地方會和這個正方形有一格的重疊, 所以最終的答案都是正確的.

uva10230.cpp
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
94
95
96
97
98
99
100
#include <cstdio>
#include <cmath>
const int MAXN = 2000;

char G[MAXN][MAXN];

typedef struct point {
    int x, y;
    point(int a, int b): x(a), y(b) {}
} Point;

bool is_in_lefttop(Point &cc, Point &pt) {
    return pt.x <= cc.x && pt.y <= cc.y;
}

bool is_in_leftbot(Point &cc, Point &pt) {
    return pt.x <= cc.x && pt.y > cc.y;
}

bool is_in_righttop(Point &cc, Point &pt) {
    return pt.x > cc.x && pt.y <= cc.y;
}

bool is_in_rightbot(Point &cc, Point &pt) {
    return pt.x > cc.x && pt.y > cc.y;
}

char charcode(Point &cc) {
    int x = ((cc.x - 1)/2) % 2;
    int y = ((cc.y - 1)/2) % 2;
    if (x == 0 && y == 0) return 'a';
    if (x == 0 && y == 1) return 'b';
    if (x == 1 && y == 0) return 'c';
    return 'd';
}

void build_GG(int len, Point lefttop, Point home) {

    Point cc(lefttop.x + len/2 - 1, lefttop.y + len/2 - 1);

    if(len == 2) {
        char c = charcode(cc);
        for(int i = 0; i < len; ++i) {
            for (int j = 0; j < len; ++j)
            {
                if(lefttop.x + i != home.x || lefttop.y+j != home.y) {
                    G[lefttop.x + i][lefttop.y+j] = c;
                }
            }
        }
        return;
    }

    int newlen = len/2;
    Point lt(cc.x, cc.y);
    Point lb(cc.x, cc.y + 1);
    Point rt(cc.x + 1, cc.y);
    Point rb(cc.x + 1, cc.y + 1);

    if(is_in_lefttop(cc, home)) {
        lt = home;
    } else if(is_in_leftbot(cc, home)) {
        lb = home;
    } else if(is_in_righttop(cc, home)) {
        rt = home;
    } else if(is_in_rightbot(cc, home)) {
        rb = home;
    }

    G[cc.x][cc.y] = 'e';
    G[cc.x][cc.y + 1] = 'e';
    G[cc.x + 1][cc.y + 1] = 'e';
    G[cc.x + 1][cc.y] = 'e';
    build_GG(newlen, lefttop, lt); // l - t
    build_GG(newlen, Point(lefttop.x, cc.y + 1), lb); // l - b
    build_GG(newlen, Point(cc.x + 1, cc.y + 1), rb); //r-b
    build_GG(newlen, Point(cc.x + 1, lefttop.y), rt); // r - t
}

int main() {

    int n, x, y;

    while(scanf("%d%d%d", &n, &x, &y) != EOF) {

        int len = pow(2, n);

        build_GG(len, Point(1, 1) , Point(x, y));
        G[x][y] = '*';

        for(int i = 1; i <= len; ++i) {
            for(int j = 1; j <= len; ++j) {
                printf("%c", G[j][i]);
            }
            printf("\n");
        }
        printf("\n");
    }
}