UVA 177 PaperFolding 종이접기 자국(분형, 귀속)

유명한 종이접기 문제: 큰 종이 한 장을 드리겠습니다. 접은 후에 다시 접고, 다시 접습니다. 매번 접을 때마다 오른쪽에서 왼쪽으로 접기 때문에 여러 번 접은 후에 원래의 큰 종이는 좁은 종이가 됩니다.지금 이 쪽지를 종이접기의 흔적을 따라 열면 매번'반쪽'만 열린다. 즉, 각 흔적을 직각으로 만들면 종이의 한쪽 끝에서 종이면과 평행하는 방향을 따라 보면 아름다운 곡선이 보인다.
종이의 방향을 정하고 규칙을 발견하기 어렵지 않은 분형이다.
실현 방면에서는 교체할 수도 있고 귀속할 수도 있다.
도형 출력에 있어서 x와 y 좌표를 저장한 다음 순서를 표시하거나 맵을 사용합니다.
 

//Rey 2015.8.3
#include
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 = 14;
const int maxL = (1<<13)+5;
int dir[maxL];
int Rotate[maxL];
int r[maxL];
int x[maxL],y[maxL];
// up right down left
// 0   1    2    3
int dx[] = {-1,0,0, 0};
int dy[] = { 0,1,0,-1};
int mx[] = { 0,0,1, 0};
int my[] = { 0,1,0,-1};
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 = (1<<n);
    // fold
    for(int i = 0, tmp[2] = {1,3}; i < N; i++) dir[i] = tmp[i&1];
    memset(Rotate,0,sizeof(int)*N);
    //open
    //mark
    for(int i = 1 ; i <= n; i++) {
        int seg = 1<<i;
        for(int j = 1<1); j  < N; j += seg<<1){
                for(int k = 0; k < seg && j+k < N; k++)
                    Rotate[j+k]++;
        }
    }

    //rotate and calculate position
    int minx = 0,miny = 0;
    x[0] = y[0] = 0;
    for(int i = 1; i < N; i++){
        int &u = dir[i] , u2 = dir[i-1];
        u = (u + Rotate[i])%4;
        x[i] = x[i-1] + dx[u2] + mx[u] ;
        y[i] = y[i-1] + dy[u2] + my[u] ;
        minx = min(minx,x[i]);
        miny = min(miny,y[i]);
    }
    //normalize
    for(int i = 0; i < N; i++){
        x[i] -= minx;
        y[i] -= miny;
    }

    for(int i = 0; i < N; i++) r[i] = i;
    sort(r,r+N,cmp);

    int prex = 0,prey = -1;
    for(int i = 0; i < N; i++){
        int id = r[i];
        if(x[id] != prex) putchar('
'),prey = -1;
        for(int j = prey+1; j < y[id]; j++) putwchar(' ');
        putchar(decode[dir[id]]);
        prey = y[id]; prex = x[id];
    }
    printf("
^
");
}


int main()
{
   // freopen("out.txt","w",stdout);
    int n;
    while(scanf("%d",&n),n){
        solve(n);
    }
    return 0;
}

 
다음으로 전송:https://www.cnblogs.com/jerryRey/p/4699728.html