UVa 177折り紙痕(Paper Folding)

あなたは折り紙が好きですか.大きな紙を1枚あげて、二つ折りにしてから二つ折りにして・・・、二つ折りのたびに右から左に折りますので、何度も折った後、元の大きな紙は狭い紙になります.今、このメモを折り紙の跡に沿って開けて、毎回「半分」だけ開けて、つまりそれぞれの跡を直角にして、紙の一端から紙面の平行方向に沿って見ると、すばらしい曲線が見えます.(自分で折ることをお勧めします)この素晴らしい曲線を描きます.
解析:実際には再帰的なプロセスであることがわかります.例えば4つの折り目しかない場合a b c dと仮定するとc=rev(a)d=bここでabcdはいずれも方向がこのように無限に再帰されていくと、始点からの痕跡方向が得られ、1つの配列に存在し、この配列に基づいて境界を求め、始点の位置を初期化し、方向に基づいて描画すればよい.細かい処理が多く、コードは長いが、非常に理解しやすく、コードに多重化された部分がある点、テストの部分は、実際にはそんなに長くありません.
コード:

#include
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
using namespace std;
const int maxn = 1e4 + 10; // 2^13 = 8192 will be enough
int a[14][maxn]; // (1 - 13) dir 
char pic[maxn][maxn];

// 0 -> right  
// 3 -> left 
// 1 -> top
// 2 -> bot
int getRev(int i) {
    return 3 - i; 
}

char change(int i) {
    if(i == 0) return 'r';
    if(i == 1) return 't';
    if(i == 2) return 'b';
    if(i == 3) return 'l';
}

//[l, r]
void dfs(int l, int r, int n) {
    if(r == l + 1) {
        a[n][l] = 0;
        a[n][r] = 1;
        return;
    }
    int mid = l + (r - l) / 2;
    dfs(l, mid, n);
    int m = (mid + 1 + r) / 2;
    for(int i = mid + 1; i <= m; i++) {
        a[n][i] = getRev(a[n][i - mid]);
    }
    for(int i = m + 1; i <= r; i++) {
        a[n][i] = a[n][i - mid];
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n && n) {
        // 0 -> right  
        // 3 -> left 
        // 1 -> top
        // 2 -> bot
        dfs(1, pow(2, n), n);
        bool dir[4]; 
        ms(dir);
        dir[a[n][1]] = true;
        int dxR = 0;
        int dxL = 0;
        int dyT = 0;
        int dyB = 0;
        int x = 0;
        int y = 0;
        for(int i = 2; i <= pow(2, n); i++) {
            if(a[n][i] == 0) {
                if(dir[1]) x--;
                y++;
            }
            if(a[n][i] == 1) {
                if(dir[1]) x--;
                else if(dir[0]) y++;
                else if(dir[3]) y--;
            }
            if(a[n][i] == 2) {
                x++;
                if(dir[0]) y++;
                else if(dir[3]) y--;
            }
            if(a[n][i] == 3) {
                if(dir[1]) x--;
                y--;
            }
            //cout << "x: " << x << " y: " << y <
            ms(dir);
            dir[a[n][i]] = true;
            dxR = max(x, dxR);
            dxL = min(x, dxL);
            dyT = max(y, dyT);
            dyB = min(y, dyB);
        }
        ms(pic);
        x = abs(dxL);
        y = abs(dyB);
        //cout << x << " " << y << endl;
        pic[x][y] = a[n][1] == 0 || a[n][1] == 3 ? '_' : '|';
        ms(dir);
        dir[a[n][1]] = true;
        for(int i = 2; i <= pow(2, n); i++) {
            if(a[n][i] == 0) {
                if(dir[1]) x--;
                y++;
            }
            if(a[n][i] == 1) {
                if(dir[1]) x--;
                else if(dir[0]) y++;
                else if(dir[3]) y--;
            }
            if(a[n][i] == 2) {
                x++;
                if(dir[0]) y++;
                else if(dir[3]) y--;
            }
            if(a[n][i] == 3) {
                if(dir[1]) x--;
                y--;
            }
            ms(dir);
            dir[a[n][i]] = true;
            pic[x][y] = a[n][i] == 0 || a[n][i] == 3 ? '_' : '|';
            //cout << "x :" << x << " y : " << y;
            //cout << pic[x][y] << " " << endl;
        }
        //cout << endl;
        int len[maxn];
        ms(len);
        for(int i = 0; i <= abs(dxL) + abs(dxR); i++) {
            for(int j = 0; j <= abs(dyB) + abs(dyT); j++) {
                if(pic[i][j]) len[i] = j;
            }
        }
        for(int i = 0; i <= abs(dxL) + abs(dxR); i++) {
            for(int j = 0; j <= len[i]; j++) {
                if(pic[i][j]) cout << pic[i][j];
                else cout << " ";
            }
            cout << endl;
        }
        cout << "^" << endl;
    }
    return 0;
}