洛谷 B4554 / B4498 菱形与画画——网格上的几何与字符画 摘要B4554 在 (2n-1)×(2n-1) 的网格上画一个空心菱形B4498 在 n×n 的网格上画一个带边框的正方形。两道题都是双层 for 循环遍历网格 条件判断该位置画什么字符。但它们的几何内核截然不同菱形靠曼哈顿距离|行-中心||列-中心|n-1决定边界位置正方形靠边界检测在不在第一行/最后一行/第一列/最后一列决定字符类型。本文从伪代码题解出发延伸到坐标几何、ASCII 艺术史、Bresenham 直线光栅化算法——从洛谷的字符网格到 GPU 渲染管线本质都是同一件事在离散网格上决定每个位置该显示什么。题目链接B4554 菱形 | B4498 画画 目录 前言 两道题在考什么 B4554菱形 思路 伪代码 关键点 B4498画画 思路 伪代码 关键点⚖️ 两题对比⚠️ 注意事项 延伸从字符网格到计算机图形学 坐标系网格就是坐标系 曼哈顿距离菱形的数学本质✏️ ASCII 艺术史 NeofetchASCII 艺术最后的黄金时代 Bresenham 直线光栅化️ 从网格到 GPU 两道题在图形学中的位置 延伸阅读文献 前言这篇题解没有源代码只有伪代码。作为一名信奥教练我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了脑子没跑通。下次遇到变体题还是不会。伪代码剥掉了语言的壳只留算法的骨架。你看不到#include看不到cin、cout看不到那些让你以为我会了的语法细节。你能看到的只有这一步做什么、下一步做什么、为什么这么做。如果你是路过的友友已经在这道题上挣扎了很久——先去喝杯水回来重新看看自己卡在哪一步。是没读懂题意是思路方向偏了还是代码有 bug 但逻辑其实对大多数时候不是不会是走偏了。偏了不可怕可怕的是偏了之后直接放弃去抄一份能 AC 的代码。抄完你以为你懂了其实你只是搬了别人的结论。除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说能理解。但平时练习给自己一点耐心。先自己想、自己写、自己调跑不过了再来看伪代码你的思路和这里差在哪一步。那一步就是你真正学到的东西。 两道题在考什么两道题都是在网格上画图形核心操作完全一样——双层 for 循环遍历每个格子用条件判断决定该格子画什么字符。但判断的依据不同B4554 菱形B4498 画画网格大小(2n-1) × (2n-1)n × n画什么空心菱形边为 ‘’内部为 ‘.’带边框正方形角 ‘’、上下边 ‘-’、左右边 ‘|’、内部 ‘*’判断依据到中心的曼哈顿距离边界检测在不在边沿几何本质|行-中心| |列-中心| n-1行0 | 行n-1 | 列0 | 列n-1难度普及−入门B4554 的菱形需要计算每个格子到中心的距离——离中心多远决定了它是不是在菱形的边上。B4498 的正方形只需要检查格子是不是在边界上——在边界上的用边框字符不在的用内部字符。一个是算距离一个是查位置。这就是两种几何思维的分水岭。 B4554菱形 B4554 思路网格大小为 size2n-1中心在 (n-1, n-1)。对每一行 i先算出它离中心行有多远d然后在这一行中‘’ 出现在距离中心列恰好 (n-1-d) 的位置——也就是列 d 和列 size-1-d。为什么因为菱形的定义是到中心的曼哈顿距离恰好等于 n-1 的点的集合。行方向已经走了 d 步列方向就只能走 n-1-d 步所以列位置是中心列 ± (n-1-d)即 d 和 size-1-d。 B4554 伪代码读取 n size 2 * n - 1 中心 n - 1 对 i 0 到 size-1: // 算当前行离中心行多远 如果 i n: d 中心 - i // 上半部分离中心越来越近 否则: d i - 中心 // 下半部分离中心越来越远 对 j 0 到 size-1: 如果 j d 或 j size - 1 - d: 输出 // 菱形边上的点 否则: 输出 . 换行 B4554 关键点d 是什么d 是当前行到中心行的距离。上半部分i n从上往下d 从 n-1 递减到 0到中心行 d0最宽的一行下半部分 d 从 0 递增回 n-1。为什么 ‘’ 在 d 和 size-1-d菱形是到中心曼哈顿距离 n-1 的点集。行方向走了 d 步列方向还剩 n-1-d 步。所以 ‘’ 在列 中心-(n-1-d) d 和列 中心(n-1-d) size-1-d。用 n4 追踪size7中心3行 id |i-3|‘’ 位置输出03j3......12j2, j4.....21j1, j5.....30j0, j6.....41j1, j5.....52j2, j4.....63j3......d0 时最宽。中心行 i3d0‘’ 在 j0 和 j6——菱形最宽的一行两端顶点。d 越大越窄到 dn-1 时只剩一个 ‘’顶/底顶点。上下对称。d 的计算方式让 i 和 size-1-i 得到相同的 d所以菱形上下对称。你只需要算上半部分下半部分自动镜像。 B4498画画 B4498 思路遍历 n×n 网格的每个格子 (i, j)根据它在哪条边上决定画什么字符四个角(0,0), (0,n-1), (n-1,0), (n-1,n-1)→ ‘’第一行或最后一行非角→ ‘-’第一列或最后一列非角→ ‘|’其他 → ‘*’这是纯粹的边界检测——不需要计算距离只需要判断在不在边界上。 B4498 伪代码读取 n 对 i 0 到 n-1: 对 j 0 到 n-1: 如果 (i0 或 in-1) 且 (j0 或 jn-1): 输出 // 四个角 否则如果 i0 或 in-1: 输出 - // 上下边非角 否则如果 j0 或 jn-1: 输出 | // 左右边非角 否则: 输出 * // 内部 换行 B4498 关键点判断顺序很重要。必须先判角再判边最后判内部。因为角也在边上——如果先判在不在第一行角会被归为 ‘-’ 而不是 ‘’。代码用if-else if链保证了这个优先级。用 n5 追踪(i,j)类型判断条件字符(0,0)左上角角条件(0,1)~(0,3)上边i0, 非角-(0,4)右上角角条件(1,0)左边j0, 非角|(1,1)~(1,3)内部都不满足*(1,4)右边jn-1, 非角|(4,0)左下角角条件(4,1)~(4,3)下边in-1, 非角-(4,4)右下角角条件输出--- |***| |***| |***| ---if-else if 的短路设计。一旦某个条件满足后面的条件不再检查。这保证了角不会被误判为边、边不会被误判为内部。如果用独立 if不用 else一个角会同时满足在第一行和在第一列两个条件输出会出错。原代码的写法可以更简洁。原代码把四个角拆成两组 if左角和右角把上下边也拆开。伪代码用(i0 或 in-1) 且 (j0 或 jn-1)一次性覆盖四个角更简洁也更不容易漏。⚖️ 两题对比B4554 菱形B4498 画画网格(2n-1) × (2n-1)n × n图形空心菱形带边框正方形判断方式算到中心的曼哈顿距离检查在不在边界几何思维距离驱动Δ行Δ列n-1位置驱动行0? 列0?对称性上下左右对称d 的计算自动镜像上下左右对称边界条件对称if-else 结构简单dj || dsize-1-j多层角→边→内部难度普及−入门菱形比正方形难因为菱形的边界不是沿网格线的——它是斜的。你没法用在不在第一行来判断必须算距离。正方形的边界沿网格线只需要检查行列号。这就是为什么 B4554 是普及−而 B4498 是入门——斜线的处理比直线难。⚠️ 注意事项B4554 的 d 计算上半部分d n-1-i下半部分d i-(n-1)。两种写法等价于d |i - (n-1)|。如果用绝对值函数代码更简洁但可读性见仁见智。B4554 的顶点处理当 d n-1顶/底行时d size-1-d两个 ‘’ 重合为一个。不需要特殊处理——j d和j size-1-d指向同一列if 条件只触发一次。B4498 的判断顺序必须先判角再判边最后判内部。用if-else if链保证优先级。如果用独立if不带 else角会被误判为边。B4498 的简化原代码把四个角分成两组 if。更简洁的写法是(i0 || in-1) (j0 || jn-1)一次覆盖四角。两题的对称性利用B4554 的 d 计算自动产生上下对称B4498 的边界条件自动产生四向对称。利用对称性可以减少代码量但 N≤100B4498和 N≤15B4554的规模下全遍历已经足够快不需要优化。 延伸从字符网格到计算机图形学你说这两道题涉及平面几何知识和可视化上的趣味性。没错——你在洛谷上用两层 for 循环画的 ‘’ 和 ‘.’和 GPU 用着色器渲染 3D 模型做的事本质上一样在离散网格上决定每个位置该显示什么。 坐标系网格就是坐标系两道题的 (i, j) 就是坐标——i 是行y 轴j 是列x 轴。你的 for 循环遍历的其实是一个坐标系j → 0 1 2 3 4 i0 . . . . ← B4554 顶行 i1 . . . i2 . . . ← 最宽行 i3 . . . i4 . . . . ← 底行这和数学课上的平面直角坐标系唯一的区别是y 轴朝下行号从上到下递增而数学课上 y 轴朝上。这个区别在计算机图形学里是标准约定——屏幕的像素坐标 (0,0) 在左上角。 曼哈顿距离菱形的数学本质B4554 的菱形数学定义是{ (i, j) : |i - 中心行| |j - 中心列| n - 1 }这是曼哈顿距离Manhattan Distance也叫 L1 距离。为什么叫曼哈顿因为曼哈顿的街道是方格网——从 A 到 B你只能横着走再竖着走不能走斜线。两点之间的曼哈顿距离就是横着走的步数加竖着走的步数欧几里得距离直线距离: √(Δx² Δy²) 曼哈顿距离方格距离: |Δx| |Δy|距离等距离曲线形状你在哪里见过欧几里得 √(Δx²Δy²)圆雷达图、信号覆盖范围曼哈顿 |Δx||Δy|菱形B4554、城市导航、棋盘距离B4554 画的菱形本质上是曼哈顿距离下的等距线——到中心距离相等的点的轨迹。欧几里得距离下等距线是圆曼哈顿距离下等距线是菱形。你画的不只是字符画是两种几何体系的可视化对比。曼哈顿距离在现实中的应用领域用途城市导航出租车计费——方格网街道的距离棋类国际象棋车的走法横竖移动Manhattan Distance — Wikipedia机器学习L1 正则化Lasso 回归——产生稀疏模型图像处理曼哈顿变换——检测菱形边缘超分辨率L1 距离做图像块匹配✏️ ASCII 艺术史你在 B4554 和 B4498 里做的事有一个正式的名字ASCII 艺术ASCII Art——用可打印字符组成图像ASCII Art — Wikipedia。历史可以分成三个阶段History of ASCII Art时期技术代表1860s打字机艺术人工在打字机上敲出图像1960s大型机行式打印机FORTRAN 程序生成波浪、螺旋等几何图形1980sBBS 时代用户手绘 ASCII 艺术签名、Logo1960 年代的研究者用 FORTRAN 写算法在行式打印机上输出结构化图像——波浪、螺旋、几何形状History of ASCII Art。你今天写的两层 for 循环和 1962 年 IBM 的 FORTRAN 程序做的是同一件事。ASCII 艺术至今仍活跃在终端界面、代码注释、BBS 签名中。它是最早的计算机图形学——在只有字符的环境里画出图像。NeofetchASCII 艺术最后的黄金时代2015 年 12 月Dylan Araps 在 GitHub 上发布了Neofetch——一个用 Bash 写的命令行系统信息工具。它在终端里显示 OS、CPU、GPU、内存等信息旁边配上对应操作系统的 ASCII LogoNeofetch — Wikipedia。Neofetch 很快成了 Linux 社区的身份认证——Reddit 的 r/unixporn 上几乎每张桌面截图都有 neofetch 的身影。GitHub stars 超过 50,000被翻译成几十种语言移植到几乎所有能跑 Bash 的平台上。然后2024 年 4 月 20 日Dylan 归档了整个仓库留下一句话Neofetch Development Ends“Have taken up farming.”我去种地了。做了近 10 年、50k stars 的项目作者不干了去当农民。没有争吵没有倦怠声明没有寻求新维护者的过渡期——就一句话干脆利落Neofetch Alternatives — Tecmint。社区之后出了多个 fork 继续维护suparious/neofetch、Ringmast4r/neofetch但官方原版就此封存。Neofetch 仍然能用只是不再更新——它成了一个时间胶囊记录着 ASCII 艺术在终端文化中的黄金时代。你在 B4554 里用 ‘’ 和 ‘.’ 画的菱形和 Neofetch 显示的 ASCII Logo用的是同一种技术——在字符网格上决定每个位置该放什么字符。区别只是你的网格是 (2n-1)×(2n-1)Neofetch 的网格是整个终端屏幕。 Bresenham 直线光栅化B4554 画的是菱形——边界是斜线。在字符网格上画斜线有一个经典问题斜线穿过一个格子时这个格子里该不该画字符1962 年Jack Bresenham 在 IBM 发明了Bresenham 直线算法Bresenham’s Line Algorithm解决了这个问题CrypTool — Geschichte// 从 (x0,y0) 到 (x1,y1) 画直线 dx |x1 - x0|, dy |y1 - y0| err dx - dy 循环: 在 (x0, y0) 画点 如果 (x0 x1 且 y0 y1): 结束 e2 2 * err 如果 e2 -dy: err - dy, x0 向 x1 方向走一步 如果 e2 dx: err dx, y0 向 y1 方向走一步Bresenham 算法只用整数加减法——没有浮点数没有乘除法。这在 1962 年的硬件上至关重要。它是计算机图形学中最先发展出来的算法Bresenham’s Algorithm — NIST至今仍是所有图形库的基础。B4554 的菱形边界本质上就是四条斜线——两条从顶到左、从顶到右两条从底到左、从底到右。你用曼哈顿距离巧妙地绕过了 Bresenham 算法但如果你要画的是任意角度的斜线比如 30°Bresenham 是标准答案。️ 从网格到 GPU从 B4554 的字符网格到 GPU 渲染 3D 游戏进化路径是这样的阶段网格单元做什么你在哪一步字符网格字符用 ‘’ 和 ‘.’ 画图B4554 / B4498像素网格像素用 RGB 值画图Bresenham 画线多边形渲染三角形顶点变换 光栅化3D 游戏着色器片段可编程管线决定每个像素的颜色现代 GPU每一步的核心操作都一样遍历网格的每个单元用某种规则决定该单元显示什么。B4554 的规则是曼哈顿距离等于 n-1 就画 ‘’“GPU 着色器的规则是根据光照、纹理、材质算出 RGB 值”。复杂度天差地别但本质都是同一个问题。你的两层 for 循环是这条进化链的第一环——光栅化Rasterization的起点。 两道题在图形学中的位置B4554 菱形B4498 画画图形学对应几何思维距离驱动位置驱动光栅化的两种思路画的图形菱形斜边正方形直边直线 vs 斜线光栅化判断条件|Δ行||Δ列|n-1行0? 列0?距离场 vs 边界检测对应算法曼哈顿距离等距线矩形边界检测SDF 渲染 / 裁剪工业应用距离场渲染、L1 正则化UI 边框渲染、碰撞检测现代图形学基础操作B4498 画的正方形边框在 UI 框架里叫border rendering——每个按钮、卡片、对话框的边框都是这么画的。B4554 的曼哈顿距离判断在图形学里叫 **SDFSigned Distance Field**的雏形——用距离函数定义形状边界。Valve 在 2007 年用 SDF 渲染字体成了现代游戏引擎的标配技术。你今天在洛谷上画 ‘’ 和 ‘.’和 Valve 渲染游戏里的字体用的是同一种思路——距离驱动。 延伸阅读文献论文与技术文档J. E. Bresenham.Algorithm for Computer Control of a Digital Plotter. IBM Systems Journal, 4(1):25-30, 1965. Bresenham’s Algorithm — NIST —— Bresenham 直线算法原始论文计算机图形学的奠基之作。C. Green.Improved alpha-tested vector textures for high-resolution 3D rendering (SDF Rendering). Valve, 2007. —— Valve 用 SDF距离场渲染字体的开创性工作B4554 曼哈顿距离的工业延伸。在线资源洛谷.B4554 [GESP202606 二级] 菱形. https://www.luogu.com.cn/problem/B4554洛谷.B4498 [GESP202603 二级] 画画. https://www.luogu.com.cn/problem/B4498Bresenham’s Line Algorithm — BlipText. https://bliptext.com/articles/bresenham-s-line-algorithm —— Bresenham 算法详解。History of ASCII Art. https://www.asciiart.eu/history-of-ascii-art —— ASCII 艺术发展史从 1860s 打字机到 BBS。ASCII Art — HandWiki. https://handwiki.org/wiki/Art:ASCII_art —— ASCII 艺术百科条目。Taxicab Geometry (Manhattan Distance) — Wikipedia. Wikipedia —— 曼哈顿距离/出租车几何的数学定义与应用。光栅化之 Bresenham 算法 — CSDN. https://blog.csdn.net/zhanxi1992/article/details/108787033 —— Bresenham 算法中文推导。CrypTool — Kryptografie Geschichte. https://www.cryptool.org/de/education/history/ —— 计算机图形学时间线。Neofetch — Wikipedia. Neofetch — HandWiki —— Neofetch 百科条目含项目历史与归档信息。Neofetch Development Ends as GitHub Project Archived. OMG! Ubuntu —— Neofetch 停更报道2024 年 5 月。Neofetch Alternatives: 3 Best Linux System Information Tools. Tecmint —— Neofetch 停更后的替代方案与社区 fork 介绍。推荐教材J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes.Computer Graphics: Principles and Practice(3rd Edition). Addison-Wesley, 2013. —— 计算机图形学圣经含光栅化、裁剪、SDF 等所有基础算法。D. Hearn, M. P. Baker.Computer Graphics with OpenGL(4th Edition). Pearson, 2010. —— OpenGL 图形学教材从 Bresenham 到 3D 渲染管线。S. Marschner, P. Shirley.Fundamentals of Computer Graphics(5th Edition). CRC Press, 2021. —— 现代图形学教材含光线追踪和 GPU 着色器。本文标签#算法 #几何 #曼哈顿距离 #ASCII艺术 #Bresenham #计算机图形学 #洛谷题解 #信奥 #C #入门本文首发于CSDN作者HugoStudio_SWAN