【递归画图】poj 2083 fractal

A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same “type” of structures must appear on all scales.
A box fractal is defined as below :
A box fractal of degree 1 is simply
X
A box fractal of degree 2 is
X X
X
X X
If using B(n - 1) to represent the box fractal of degree n - 1, then a box fractal of degree n is defined recursively as following
B(n - 1) B(n - 1)

B(n - 1)

B(n - 1) B(n - 1)

Your task is to draw a box fractal of degree n.

The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last line of input is a negative integer −1 indicating the end of input.

For each test case, output the box fractal using the ‘X’ notation. Please notice that ‘X’ is an uppercase letter. Print a line with only a single dash after each test case.

1
2
3
4
-1

X
-
X X
X
X X
-
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
-
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
-

Shanghai 2004 Preliminary

根据样例画图。

最小子图就是X，若当前是最小子图就在当前位置画一个X，
若不是，当前图下五个最小子图的位置，继续递归。

预处理 + printf TLE
预处理 + putchar 15ms
直接putchar 0ms

Problem: 2083 User: pengrj
Memory: 4668K Time: 0MS
Language: G++ Result: Accepted

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

#include <cstdio>
using namespace std;
int a[8][1000][1000];

void (int size, int x, int y, int i)
{
    int m = 1;
    for (int j = 0; j < i - 2; j++)
        m *= 3;

    if (i == 1)
        a[size][x][y] = 1;
    else
    {
        print(size, x, y, i - 1);
        print(size, x, y + m * 2, i - 1);
        print(size, x + m, y + m, i - 1);
        print(size, x + 2 * m, y, i - 1);
        print(size, x + 2 * m, y + 2 * m, i - 1);
    }
}

void solve(void)
{
    int n;
    while (scanf("%d", &n), n != -1)
    {
        print(n, 0, 0, n);
        int size = pow(3, n - 1);
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
            {
                a[n][i][j] == 1 ? putchar('X') : putchar(' ');
                if (j == size - 1)
                    puts("");
            }
        printf("-n");
    }
}

int main(void)
{
    solve();
    return 0;
}