题目链接

算法竞赛进阶指南-31.分形

分形，具有以非整数维形式充填空间的形态特征。

通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。

现在，定义“盒子分形”如下：

一级盒子分形：

X

二级盒子分形：

X X
 X
X X

如果用 $B(n - 1)$ 代表第 $n-1$ 级盒子分形，那么第 $n$ 级盒子分形即为：

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

        B(n - 1)

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

你的任务是绘制一个 $n$ 级的盒子分形。

输入格式

输入包含几个测试用例。

输入的每一行包含一个不大于 $7$ 的正整数 $n$，代表要输出的盒子分形的等级。

输入的最后一行为 $-1$，代表输入结束。

输出格式

对于每个测试用例，使用 X 符号输出对应等级的盒子分形。

请注意 X 是一个大写字母。

每个测试用例后输出一个独立一行的短划线。

输入样例：

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
-

---

Method : 递归

题意很明显的递归嵌套，递归的时候要注意每次offset的变化规律。

不要在dfs内打印：在dfs内直接打印容易出现换行问题。
可以先用二维数组存储是否打印(相当于记忆化cache)，等dfs完再一起打印。

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N = (int)pow(3, 7) + 7;

bool g[N][N];

void draw(int n, int x, int y) {
    if (n == 1) {
        g[x][y] = true;
        return;
    }
    int offset = (int)pow(3, n - 2); // (n - 1)级的offset
    draw(n - 1, x, y);                          // 左上
    draw(n - 1, x + 2 * offset, y);             // 右上
    draw(n - 1, x + offset, y + offset);        // 正中
    draw(n - 1, x, y + 2 * offset);             // 左下
    draw(n - 1, x + 2 * offset, y + 2 *offset); // 右下
}

int main() {
    memset(g, false, sizeof g);
    draw(7, 1, 1);

    int n;
    while (cin >> n) {
        if (n == -1) break;
        int len = (int)pow(3, n - 1);
        for (int i = 1; i <= len; i ++) {
            for (int j = 1; j <= len; j++) {
                if (g[i][j]) printf("X");
                else printf(" ");               
            }
            puts("");
        }
        puts("-");
    }

    return 0;
}

复杂度分析

• 时间复杂度：${O(5^7)}$， 递归5叉树，树的深度是7。

• 空间复杂度：${O(n^2)}$，主要用于g[N][N]。

参考:

https://www.acwing.com/solution/content/823/