UVA 177 Paper Folding

题目分析本题描述了一个有趣的折纸问题将一张长纸条进行NNN次对折每次将右半部分折到左边然后每个折痕从180∘180^\circ180∘打开到90∘90^\circ90∘从纸的边缘端视会观察到一条被称为 “龙曲线” Dragon Curve\texttt{Dragon Curve}Dragon Curve 的图形。要求根据输入的NNN绘制出对应的曲线其中水平线段用下划线_表示竖直线段用竖线|表示。输入包含多行每行一个整数NNN1≤N≤131 \leq N \leq 131≤N≤13以000表示输入结束。对于每个NNN输出对应的龙曲线图形且图形需要尽可能靠左、靠上放置每个图形后跟一行包含单个^的行作为结束标记。解题思路1. 折痕序列的生成规律龙曲线的形成与折痕的方向序列密切相关。经过分析可以发现折痕序列的生成具有自相似性分形特征。定义四种基本方向R\texttt{R}R向右L\texttt{L}L向左U\texttt{U}U向上D\texttt{D}D向下经过一次折叠的折痕序列为RU\texttt{RU}RU。对于NNN次折叠其折痕序列可以通过N−1N-1N−1次折叠的序列生成pattern(N) pattern(N-1) 0 rotate(pattern(N-1))其中rotate\texttt{rotate}rotate表示将序列中每个字符按规则映射R→U\texttt{R} \rightarrow \texttt{U}R→UU→L\texttt{U} \rightarrow \texttt{L}U→LL→D\texttt{L} \rightarrow \texttt{D}L→DD→R\texttt{D} \rightarrow \texttt{R}D→R然后反转顺序。实际代码中我们使用递归方式生成序列先得到N−1N-1N−1的序列然后将其反转并映射后追加到自身末尾。2. 坐标绘制得到折痕序列后从起点开始模拟绘制过程遇到R\texttt{R}R或L\texttt{L}L时绘制水平线段_并相应改变yyy坐标遇到U\texttt{U}U或D\texttt{D}D时绘制竖直线段|并相应改变xxx坐标由于折痕打开后线段之间是连续的需要注意绘制位置和坐标更新的顺序绘制过程中记录所有访问点的坐标范围最后只输出有图形的区域并且尽可能靠左、靠上。3. 实现细节使用二维字符数组matrix存储图形大小设置为1024×10241024 \times 10241024×1024足够容纳N13N13N13的图形起点坐标设为(512,512)(512, 512)(512,512)以避免负坐标输出时逐行扫描去掉每行末尾多余的空格代码实现// Paper Folding// UVa ID: 177// Verdict: Accepted// Submission Date: 2016-03-11// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 方向映射表用于生成折叠序列的反转部分mapchar,charmapped;// 存储绘制图形的二维数组charmatrix[1024][1024];// 递归生成 N 次折叠后的折痕方向序列stringunfolding(intn){if(n1){// 先获取 N-1 次折叠的序列string patternunfolding(n-1);intlengthpattern.length();// 将原序列反转并映射后追加到末尾for(intilength-1;i0;i--)patternmapped[pattern[i]];returnpattern;}else// 一次折叠的基本序列为 RUreturnRU;}// 根据折痕序列绘制龙曲线voiddisplay(intn){// 获取完整的折痕序列末尾添加 0 作为哨兵string patternunfolding(n);pattern0;// 初始化图形数组为空格memset(matrix, ,sizeof(matrix));intx512,y512;// 起始坐标取中间位置避免负坐标intminx512,maxx512,miny512,maxy512;// 遍历折痕序列绘制图形for(inti0;ipattern.length()-1;i){if(pattern[i]L){// 向左画水平线matrix[x][y]_;y-1;}elseif(pattern[i]R){// 向右画水平线matrix[x][y]_;y1;}elseif(pattern[i]U){// 向上画竖直线matrix[x][y]|;x-1;// 根据下一个方向确定转角后的位置if(pattern[i1]L)y-1;if(pattern[i1]R)y1;}elseif(pattern[i]D){// 向下画竖直线x1;matrix[x][y]|;// 根据下一个方向确定转角后的位置if(pattern[i1]L)y-1;if(pattern[i1]R)y1;}// 更新坐标边界minxmin(x,minx);maxxmax(x,maxx);minymin(y,miny);maxymax(y,maxy);}// 输出图形尽可能靠左、靠上for(intiminx;imaxx;i){intlastymaxy;// 去掉行尾多余的空格while(matrix[i][lasty] )lasty--;if(lasty0){for(intjminy;jlasty;j)coutmatrix[i][j];cout\n;}}// 每个图形以 ^ 结束cout^\n;}intmain(){cin.tie(0);cout.sync_with_stdio(false);// 初始化方向映射表mapped.insert(make_pair(R,U));mapped.insert(make_pair(U,L));mapped.insert(make_pair(L,D));mapped.insert(make_pair(D,R));intn;while(cinn,n)display(n);return0;}总结本题的核心在于发现龙曲线折痕序列的自相似生成规律。通过递归方式生成序列后模拟绘制过程即可得到答案。对于N13N13N13图形宽度会超过808080个字符但题目允许这种情况只需要正确输出即可。