UVA 177 PaperFolding 折纸痕 （分形，递归）

著名的折纸问题：给你一张很大的纸，对折以后再对折，再对折……每次对折都是从右往左折，因此在折了很多次以后，原先的大纸会变成一个窄窄的纸条。现在把这个纸条沿着折纸的痕迹打开，每次都只打开“一半”，即把每个痕迹做成一个直角，那么从纸的一端沿着和纸面平行的方向看过去，会看到一条美妙的曲线。

就是一个分形，规定一下，纸的朝向，然后不难发现规律。

实现方面，可以迭代也可递归。

在图形输出方面，存下x和y坐标，然后下标排个序，或者用map。

//Rey 2015.8.3

#include<bits/stdc++.h>

using namespace std;

// r -> rl -> open -> ru

//   -> rlrl -> open -> r ud l -> open -> ru lu

//   -> rlrlrlrl -> open -> r ud lr ud l -> open -> ru ludr dl -> rulu ldlu

//   -> rlrlrlrlrlrlrlrl -> r ud lr ud lr ud lr ud l -> ru

const int maxn = ;

const int maxL = (<<)+;

int dir[maxL];

int Rotate[maxL];

int r[maxL];

int x[maxL],y[maxL];

// up right down left

// 0   1    2    3

int dx[] = {-,,, };

int dy[] = { ,,,-};

int mx[] = { ,,, };

int my[] = { ,,,-};

char decode[] = {'|','_','|','_'};

bool cmp(int a,int b) { return x[a] < x[b] || ( x[a] == x[b] && y[a] < y[b] ); }

void solve(int n)

{

    int N = (<<n);

    // fold

    for(int i = , tmp[] = {,}; i < N; i++) dir[i] = tmp[i&];

    memset(Rotate,,sizeof(int)*N);

    //open

    //mark

    for(int i =  ; i <= n; i++) {

        int seg = <<i;

        for(int j = <<(i-); j  < N; j += seg<<){

                for(int k = ; k < seg && j+k < N; k++)

                    Rotate[j+k]++;

        }

    }

    //rotate and calculate position

    int minx = ,miny = ;

    x[] = y[] = ;

    for(int i = ; i < N; i++){

        int &u = dir[i] , u2 = dir[i-];

        u = (u + Rotate[i])%;

        x[i] = x[i-] + dx[u2] + mx[u] ;

        y[i] = y[i-] + dy[u2] + my[u] ;

        minx = min(minx,x[i]);

        miny = min(miny,y[i]);

    }

    //normalize

    for(int i = ; i < N; i++){

        x[i] -= minx;

        y[i] -= miny;

    }

    for(int i = ; i < N; i++) r[i] = i;

    sort(r,r+N,cmp);

    int prex = ,prey = -;

    for(int i = ; i < N; i++){

        int id = r[i];

        if(x[id] != prex) putchar('\n'),prey = -;

        for(int j = prey+; j < y[id]; j++) putwchar(' ');

        putchar(decode[dir[id]]);

        prey = y[id]; prex = x[id];

    }

    printf("\n^\n");

}

int main()

{

   // freopen("out.txt","w",stdout);

    int n;

    while(scanf("%d",&n),n){

        solve(n);

    }

    return ;

}