【题目来源】

洛谷：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 = 3n=3时，图形如下：

..+.. .+.+. +...+ .+.+. ..+..

【输入】

输入一个正整数n nn；

【输出】

输出2 n − 1 2n - 12n−1行，表示按要求画的菱形。

【输入样例】

4

【输出样例】

...+... ..+.+.. .+...+. +.....+ .+...+. ..+.+.. ...+...

【核心思想】

1. 问题分析：给定正整数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)，边框由+组成，其余位置为.。关键观察是：菱形的上半部分和下半部分关于中心行对称，每行的+出现在两个对称位置，且距离中心列的偏移量随远离中心而增大。

2. 算法选择：

   • 对称绘制法：将菱形分为上半部分（含中心行）和下半部分（含中心行），利用对称性分别绘制
   • 边界收缩/扩展：用双指针l ll和r rr表示当前行菱形边框的左右列坐标，上半部分l ll递减、r rr递增，下半部分同理

3. 关键步骤：

   • 初始化画布：创建( 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 = nl=r=n
   • 绘制上半部分（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−1，r ← r + 1 r \leftarrow r + 1r←r+1（下一行菱形变宽）
   • 绘制下半部分（i ii从2 n − 1 2n-12n−1到n nn）：
     • 重置l = r = n l = r = nl=r=n，从底部向中心行绘制
     • 在( i , l ) (i, l)(i,l)和( i , r ) (i, r)(i,r)处标记+
     • l ← l − 1 l \leftarrow l - 1l←l−1，r ← r + 1 r \leftarrow r + 1r←r+1（上一行菱形变宽）
   • 输出画布：按行输出矩阵

4. 时间/空间复杂度：

   • 时间复杂度：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)的画布矩阵

5. 对称绘制法的核心思想：

   • 几何对称性利用：菱形关于水平中心线和垂直中心线均对称，因此只需计算一侧的坐标规律，通过对称复制完成另一半
   • 双指针控制边界：l ll和r rr从中心列向两侧扩展，每行偏移量增加1 11，精确刻画菱形边框的斜线特征（斜率为± 1 \pm 1±1）
   • 先填充后覆盖：先将整个画布置为.，再在特定位置覆盖+，避免复杂的条件判断，简化绘制逻辑
   • 中心行重复绘制：上半部分和下半部分的循环均包含中心行，导致中心行的两个+被绘制两次（效果相同），代码简洁但存在冗余
   • 适用于规则几何图形的字符画绘制，尤其是具有对称性的多边形边框生成

【算法标签】

#普及- #模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=20;// 常量：数组最大尺寸chara[2*N][2*N];// a[i][j]: 画布上第 i 行第 j 列的字符intn;// n: 菱形边长intmain(){cin>>n;// 读入菱形边长 nfor(inti=1;i<=2*n-1;i++)// 初始化画布：全部填充为 '.'for(intj=1;j<=2*n-1;j++)a[i][j]='.';// 空白网格用 '.' 表示intx=n;// x: 菱形的中心行（同时也是中心列）intl=x,r=x;// l: 当前行菱形左边界列; r: 当前行菱形右边界列for(inti=1;i<=x;i++)// 绘制菱形的上半部分（含中心行）{a[i][l]='+',a[i][r]='+';// 在当前行左右边界标记 '+'l--,r++;// 下一行左边界左移，右边界右移，菱形逐渐变宽}l=x,r=x;// 重置左右边界到中心列for(inti=2*n-1;i>=x;i--)// 绘制菱形的下半部分（含中心行）{a[i][l]='+',a[i][r]='+';// 在当前行左右边界标记 '+'l--,r++;// 上一行左边界左移，右边界右移，菱形逐渐变宽}for(inti=1;i<=2*n-1;i++)// 输出画布{for(intj=1;j<=2*n-1;j++)cout<<a[i][j];// 输出第 i 行第 j 列的字符cout<<endl;// 每行输出后换行}return0;}

【运行结果】

4 ...+... ..+.+.. .+...+. +.....+ .+...+. ..+.+.. ...+...