Uva 177 Paper Folder 题解
本题是著名的折纸痕问题。。本是练习递归，但是我觉得模拟的成分更大。暂把它归为模拟题。
Url：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=113
XXX 说，模拟题是最简单的，我觉得模拟题其实是最难做的。
#include <iostream>#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;#define Max 15int turn[1<<Max];//折痕的方向，0代表顺时针，1代表逆时针int x[Max],y[Max];//每个示例对应的"S"的坐标int w[Max],h[Max];//每个示例对应的宽度和高度char map[Max][150][250];//第二维和第三维最大值可以有getPos()函数计算，k = 13即可int width[Max][150];//由于有些忽略空格，width必须计算void getTurn(int l,int r,int x,int dir){ turn[x] = dir; if(l == r) { return; } getTurn(l,x-1,(x-1+l)>>1,0); getTurn(x+1,r,(r+x+1)>>1,1);}void getPos(int &x,int &y,int &w,int &h,int n){ int dir = 0; int xx = 0,yy = 0; int pos_x = 0,pos_y = 0; int nec_x = 0,nec_y = 0; for(int i=0; i<n; i++) { //顺时针 if(turn[i] == 0) { if(dir == 0) { yy++; } else if(dir == 1) { xx--; yy--; } else if(dir == 2) { xx++; yy--; } else if(dir == 3) { yy++; } dir = (dir + 1)%4; } //逆时针 else if(turn[i] == 1) { if(dir == 0) { xx++; yy++; } else if(dir == 1) { xx--; yy++; } else if(dir == 2) { yy--; } else if(dir == 3) { yy--; } dir = (dir - 1 + 4)%4; } if(xx>=0) { pos_x = max(pos_x,xx); } else { nec_x = min(nec_x,xx); } if(yy>=0) { pos_y = max(pos_y,yy); } else { nec_y = min(nec_y,yy); } } w = pos_y - nec_y + 1; h = pos_x - nec_x + 1; x = -nec_x; y = -nec_y; //printf("w = %d,h = %d,x = %d,y = %d\n",w,h,x,y);}void getFill(int k,int x,int y,int n){ int xx = x,yy = y; int dir = 0; map[k][xx][yy] = '_'; width[k][xx]=max(width[k][xx],yy); for(int i=0; i<n; i++) { //顺时针 if(turn[i] == 0) { if(dir == 0) { yy++; map[k][xx][yy] = '|'; } else if(dir == 1) { xx--; yy--; map[k][xx][yy] = '_'; } else if(dir == 2) { xx++; yy--; map[k][xx][yy] = '|'; } else if(dir == 3) { yy++; map[k][xx][yy] = '_'; } dir = (dir + 1)%4; } //逆时针 else if(turn[i] == 1) { if(dir == 0) { xx++; yy++; map[k][xx][yy] = '|'; } else if(dir == 1) { xx--; yy++; map[k][xx][yy] = '_'; } else if(dir == 2) { yy--; map[k][xx][yy] = '|'; } else if(dir == 3) { yy--; map[k][xx][yy] = '_'; } dir = (dir - 1 + 4)%4; } width[k][xx]=max(width[k][xx],yy); }}void getPrint(int k){ for(int i=0;i<h[k];i++) { for(int j=0;j<=width[k][i];j++) { if(map[k][i][j] == 0) { printf(" "); } else { printf("%c",map[k][i][j]); } } printf("\n"); } printf("^\n");}void solve(int k){ int n = (1<<k) - 1;//折痕的数目 getTurn(0,n-1,(n-1)>>1,0); getPos(x[k],y[k],w[k],h[k],n); getFill(k,x[k],y[k],n); getPrint(k);}int main(){#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);#endif int k; memset(map,0,sizeof(map)); while(true) { scanf("%d",&k); if(k == 0) { break; } solve(k); } return 0;}