本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-13 15:22:05

[UVA177] Paper Folding

Problem Statement

给定一张无限大的纸，从右往左对折 $N$ 次，形成狭长的纸条。接下来，每次沿着折痕展开，但是仅展开 $90\degree$，形成立体图形。输出展开后水平看所得到的图案。

数据范围：$1\le N\le 13$。

Solution

考虑每次展开 $90\degree$ 等价于将原图形复制一份并旋转 $90\degree$，比如说：

而最终会展开 $N$ 次。所以，考虑对于一个图形，如何将其旋转 $90\degree$ 的图形对应填充上，而且 $\tt \$ 变 $\tt |$，$\tt |$ 变 $\tt \$。直接处理并不好搞，不过这些线可以转化为一定的方向，比如说初始为向右，接下来是向右向上，然后是向右向上向左向上，再者向右向上向左向上向左向下向左向上……。

不难发现，这一次会在上一次的基础上倒着再做一遍，只是这时候方向都逆时针旋转了 $90\degree$。比如说：

• 倒着做一遍是向右，方向逆时针旋转 $90\degree$ 为向上：向右向上。
• 倒着做一遍是向上向右，方向逆时针旋转 $90\degree$ 为向左向上：向右向上向左向上。
• 倒着做一遍是向上向左向上向右，方向逆时针旋转 $90\degree$ 为向左向下向左向上：向右向上向左向上向左向下向左向上。
• ……

接下来考虑实现，由于并不知道图究竟有多大。所以，直接开 $1000\times 1000$ 的图，初始在 $(500,500)$ 的位置填 $\tt \_$，接下来按照上述方式暴力填位置即可，由于题目输出要求比较特殊，只需要预处理一张 $4\times 2$ 的表，表示从 $4$ 个方向移动到另外两个垂直方向横纵坐标的变化即可。输出表的时候，先将覆盖整张图的最小矩形计算出来，然后对于每行，仅输出到最后一个字符。

时间复杂度：$O(2^N)$。

Code

#include <bits\/stdc++.h>
using namespace std;

int main() {
    int n;
    while (cin >> n && n) {
        vector<vector<char>> ans(1000, vector<char>(1000, ' '));
        vector<vector<int>> dx = {{1, 1}, {1, -1}, {-1, -1}, {1, -1}}, dy = {{0, 1}, {-1, -1}, {0, 1}, {0, 0}};
        ans[500][500] = '_';
        int x = 500, y = 500, lst = 0;
        vector<int> sd = {0};
        while (n -- ) {
            vector<int> cur;
            reverse(sd.begin(), sd.end());
            for (auto v : sd) {
                int u = (v + 1) % 4;
                x += dx[lst][u \/ 2], y += dy[lst][u \/ 2];
                if (u % 2 == 0) ans[y][x] = '_';
                else ans[y][x] = '|';
                cur.push_back(u), lst = u;
            }
            reverse(sd.begin(), sd.end());
            sd.insert(sd.end(), cur.begin(), cur.end());
        }

        int lx = 2000, ly = 2000, rx = -1;
        vector<int> r(1000);
        for (int i = 1; i < 1000; i ++)
            for (int j = 1; j < 1000; j ++)
                if (ans[i][j] != ' ') {
                    lx = min(lx, i), ly = min(ly, j);
                    rx = max(rx, i), r[i] = max(r[i], j);
                }

        for (int i = lx; i <= rx; i ++) {
            for (int j = ly; j <= r[i]; j ++)
                cout << ans[i][j];
            cout << endl;
        }
        cout << "^\n";
    }
}