题解：洛谷 B4554 [GESP202606 二级] 菱形

【题目来源】洛谷B4554 [GESP202606 二级] 菱形 - 洛谷【题目描述】给定正整数n nn在( 2 n − 1 ) × ( 2 n − 1 ) (2n - 1) \times (2n - 1)(2n−1)×(2n−1)个网格的画布中使用字符画一个边长为n nn个网格的菱形。其中空白网格使用⋅ \cdot⋅表示菱形边所在的网格用 表示。例如当n 3 n 3n3时图形如下.... ... ... ... ....【输入】输入一个正整数n nn【输出】输出2 n − 1 2n - 12n−1行表示按要求画的菱形。【输入样例】4【输出样例】...... ..... ..... ..... ..... ..... ......【核心思想】问题分析给定正整数n nn在( 2 n − 1 ) × ( 2 n − 1 ) (2n-1) \times (2n-1)(2n−1)×(2n−1)的画布上绘制边长为n nn的菱形边框。菱形中心位于画布中心( n , n ) (n, n)(n,n)边框由组成其余位置为.。关键观察是菱形的上半部分和下半部分关于中心行对称每行的出现在两个对称位置且距离中心列的偏移量随远离中心而增大。算法选择对称绘制法将菱形分为上半部分含中心行和下半部分含中心行利用对称性分别绘制边界收缩/扩展用双指针l ll和r rr表示当前行菱形边框的左右列坐标上半部分l ll递减、r rr递增下半部分同理关键步骤初始化画布创建( 2 n − 1 ) × ( 2 n − 1 ) (2n-1) \times (2n-1)(2n−1)×(2n−1)的字符矩阵全部填充为.确定中心中心位置为( n , n ) (n, n)(n,n)初始化l r n l r nlrn绘制上半部分i ii从1 11到n nn在( i , l ) (i, l)(i,l)和( i , r ) (i, r)(i,r)处标记l ← l − 1 l \leftarrow l - 1l←l−1r ← r 1 r \leftarrow r 1r←r1下一行菱形变宽绘制下半部分i ii从2 n − 1 2n-12n−1到n nn重置l r n l r nlrn从底部向中心行绘制在( i , l ) (i, l)(i,l)和( i , r ) (i, r)(i,r)处标记l ← l − 1 l \leftarrow l - 1l←l−1r ← r 1 r \leftarrow r 1r←r1上一行菱形变宽输出画布按行输出矩阵时间/空间复杂度时间复杂度O ( n 2 ) O(n^2)O(n2)初始化画布O ( n 2 ) O(n^2)O(n2)绘制边框O ( n ) O(n)O(n)输出O ( n 2 ) O(n^2)O(n2)空间复杂度O ( n 2 ) O(n^2)O(n2)存储( 2 n − 1 ) × ( 2 n − 1 ) (2n-1) \times (2n-1)(2n−1)×(2n−1)的画布矩阵对称绘制法的核心思想几何对称性利用菱形关于水平中心线和垂直中心线均对称因此只需计算一侧的坐标规律通过对称复制完成另一半双指针控制边界l ll和r rr从中心列向两侧扩展每行偏移量增加1 11精确刻画菱形边框的斜线特征斜率为± 1 \pm 1±1先填充后覆盖先将整个画布置为.再在特定位置覆盖避免复杂的条件判断简化绘制逻辑中心行重复绘制上半部分和下半部分的循环均包含中心行导致中心行的两个被绘制两次效果相同代码简洁但存在冗余适用于规则几何图形的字符画绘制尤其是具有对称性的多边形边框生成【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;constintN20;// 常量数组最大尺寸chara[2*N][2*N];// a[i][j]: 画布上第 i 行第 j 列的字符intn;// n: 菱形边长intmain(){cinn;// 读入菱形边长 nfor(inti1;i2*n-1;i)// 初始化画布全部填充为 .for(intj1;j2*n-1;j)a[i][j].;// 空白网格用 . 表示intxn;// x: 菱形的中心行同时也是中心列intlx,rx;// l: 当前行菱形左边界列; r: 当前行菱形右边界列for(inti1;ix;i)// 绘制菱形的上半部分含中心行{a[i][l],a[i][r];// 在当前行左右边界标记 l--,r;// 下一行左边界左移右边界右移菱形逐渐变宽}lx,rx;// 重置左右边界到中心列for(inti2*n-1;ix;i--)// 绘制菱形的下半部分含中心行{a[i][l],a[i][r];// 在当前行左右边界标记 l--,r;// 上一行左边界左移右边界右移菱形逐渐变宽}for(inti1;i2*n-1;i)// 输出画布{for(intj1;j2*n-1;j)couta[i][j];// 输出第 i 行第 j 列的字符coutendl;// 每行输出后换行}return0;}【运行结果】4 ...... ..... ..... ..... ..... ..... ......