「UVA177」折纸痕 Paper Folding

· · 题解

[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。比如说：

接下来考虑实现，由于并不知道图究竟有多大。所以，直接开 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";
    }
}