洛谷 B4501 / B4557 山之谷与扫雷——八方向邻居检查与一个经典游戏的故事 摘要B4501 在 N×M 网格中找山谷海拔 ≤ 全部 8 个邻居B4557 在 N×M 网格中数每个格子周围 8 个方向有几个雷。两道题共享同一个核心操作——八方向邻居遍历——只是一个做全部比较另一个做计数。这个操作不是程序员发明的它来自一个 1989 年诞生的经典游戏——扫雷。本文从伪代码题解出发讲述扫雷从 1973 年的Cube到 1989 年 Curt Johnson 的 OS/2 学习项目、从 1990 年的 Entertainment Pack 到 1992 年随 Windows 3.1 进入每一台 PC 的完整故事——以及教你用鼠标这个被遗忘的设计意图。题目链接B4501 山之谷 | B4557 扫雷 目录 前言 两道题在考什么⛰️ B4501山之谷 思路 伪代码 关键点 B4557扫雷 思路 伪代码 关键点⚖️ 两题对比⚠️ 注意事项 延伸扫雷的故事——从 1973 到今天 前身1973-1985 1989 年的学习项目 1990-1992从 Entertainment Pack 到 Windows 3.1️ 教你用鼠标的设计意图 1999-2001禁雷运动 2012 至今离开默认安装活在到处 八方向邻居检查从游戏到算法 延伸阅读文献 前言这篇题解没有源代码只有伪代码。作为一名信奥教练我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了脑子没跑通。下次遇到变体题还是不会。伪代码剥掉了语言的壳只留算法的骨架。你看不到#include看不到cin、cout看不到那些让你以为我会了的语法细节。你能看到的只有这一步做什么、下一步做什么、为什么这么做。如果你是路过的友友已经在这道题上挣扎了很久——先去喝杯水回来重新看看自己卡在哪一步。是没读懂题意是思路方向偏了还是代码有 bug 但逻辑其实对大多数时候不是不会是走偏了。偏了不可怕可怕的是偏了之后直接放弃去抄一份能 AC 的代码。抄完你以为你懂了其实你只是搬了别人的结论。除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说能理解。但平时练习给自己一点耐心。先自己想、自己写、自己调跑不过了再来看伪代码你的思路和这里差在哪一步。那一步就是你真正学到的东西。 两道题在考什么两道题共享一个核心操作八方向邻居遍历。对于一个格子 (i, j)检查它的上、下、左、右、左上、右上、左下、右下最多 8 个邻居。B4501 山之谷B4557 扫雷网格内容海拔高度雷-1或空对每个格子做什么检查自己 ≤ 全部邻居数邻居中有几个雷八方向用途全部比较求最小计数求有几个边界处理只检查存在的邻居只检查存在的邻居核心模式极值判定邻居计数B4501 的山谷定义是海拔 ≤所有8 个邻居。只要有一个邻居比自己低就不是山谷。这是全部满足的判断——continue提前退出。B4557 的扫雷定义是非雷格子的值 8 个邻居中雷的个数。这是逐个计数——遍历 8 个方向碰到雷就sum。同一个八方向遍历一个做比较一个做计数。这两道题就是扫雷游戏的两个面B4557 是扫雷的正面生成数字B4501 是扫雷的背面找极值点。⛰️ B4501山之谷 B4501 思路遍历每个格子 (i, j)检查它的 8 个方向的邻居。如果所有存在的邻居的海拔都 ≥ 当前格子则当前格子是山谷。任何一个邻居比当前格子低就不是山谷——立刻continue跳到下一个格子。 B4501 伪代码读取 N, M 读取网格 map[0..N-1][0..M-1] 山谷数 0 对 i 0 到 N-1: 对 j 0 到 M-1: 是山谷 true // 检查 8 个方向上、下、左、右、左上、右上、左下、右下 对每个方向 (di, dj) ∈ {(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)}: ni i di nj j dj 如果 0 ≤ ni N 且 0 ≤ nj M: // 邻居存在 如果 map[i][j] map[ni][nj]: // 比邻居高不是山谷 是山谷 false 跳出方向循环 如果 是山谷: 山谷数 输出 山谷数 B4501 关键点八方向遍历的统一写法。原始代码对每个方向单独写ifcontinue8 段重复代码。更简洁的写法是定义一个方向数组dirs [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]用一个循环遍历所有方向。而非。山谷的定义是海拔不高于邻居——map[i][j] map[ni][nj]。如果两个相邻格子海拔相同两个都可能是山谷都 ≤ 对方。提前剪枝。任何一个方向不满足就continue跳出当前格子的检查不需要检查完所有 8 个方向。原始代码用continue跳过后续检查——这是短路思维一个条件不满足就不可能是山谷何必继续查。1×1 特殊情况。如果 N1, M1唯一的格子没有邻居默认是山谷。原始代码单独处理了这种情况。用样例追踪3×5 网格7 6 6 7 9 6 5 6 7 6 6 5 7 8 9格子海拔邻居最小值≤ 所有邻居山谷(0,0)76右、下、右下否76否(1,1)55左上6、上6、右上6、左6、右6、左下6、下5、右下7是5≤全部是(2,1)55同上类似是是(1,4)66左上7、上9、左7、左下8、下9是6≤全部是输出3。 B4557扫雷 B4557 思路先读入雷的坐标在网格中标记为 -1。然后遍历每个非雷格子检查 8 个方向的邻居数有几个是 -1雷把计数写入当前格子。雷格子直接输出*。 B4557 伪代码读取 N, M, Q 数组 grid[0..N-1][0..M-1] 初始化为 0 对 i 1 到 Q: 读取 x, y // 行号从 1 开始 grid[x-1][y-1] -1 // 转为 0 基下标标记为雷 对 i 0 到 N-1: 对 j 0 到 M-1: 如果 grid[i][j] -1: 输出 * 空格 否则: 雷数 0 对每个方向 (di, dj) ∈ 8个方向: ni i di nj j dj 如果 0 ≤ ni N 且 0 ≤ nj M: // 邻居存在 如果 grid[ni][nj] -1: // 邻居是雷 雷数 grid[i][j] 雷数 输出 雷数 空格 输出 换行 B4557 关键点行号从 1 开始。题目说行号和列号均从 1 开始但 C 数组从 0 开始。读入坐标后要x-1, y-1转换。-1 标记雷。用 -1 表示这里是雷非雷格子初始化为 0。计数时检查邻居是否 -1。这种用一个特殊值表示特殊状态的手法叫哨兵值Sentinel Value。雷格子和非雷格子的分支。雷格子直接输出*非雷格子计算邻居雷数后输出数字。两种格子在同一双重循环里用if-else分开处理。用样例追踪3×4 网格4 个雷雷的位置(1,1) (1,3) (2,4) (3,2) 转为 0 基(0,0) (0,2) (1,3) (2,1) * . * . * 2 * 2 . . . * → 2 3 3 * . * . . 1 * 2 1以格子 (0,1) 为例8 个邻居是 (0,0)雷, (0,2)雷, (1,0), (1,1), (1,2)其中 2 个雷 → 输出 2。以格子 (1,1) 为例8 个邻居是 (0,0)雷, (0,1), (0,2)雷, (1,0), (1,2), (2,0), (2,1)雷, (2,2)其中 3 个雷 → 输出 3。⚖️ 两题对比B4501 山之谷B4557 扫雷网格含义海拔高度雷-1或空对邻居做什么比较≤ 全部计数有几个雷判断类型“全部满足” → 极值判定“逐个累加” → 邻居计数提前退出是一个不满足就 continue否必须数完 8 个方向特殊格子无雷格子输出*不计数复杂度O(N×M×8) O(N×M)O(N×M×8) O(N×M)两道题的时间复杂度相同——都是 O(N×M)因为 8 是常数。区别在于对邻居信息的使用方式B4501 做布尔判断全部满足一个不满足就退出B4557 做整数累加有几个必须数完。这就是扫雷游戏的两面生成数字B4557和判断极值B4501用的是同一个八方向遍历操作只是对遍历结果的处理方式不同。⚠️ 注意事项B4557 的边界检查顺序遍历邻居时务必先检查边界再访问数组。正确写法是if(i - 1 0 a[i-1][j] -1)——先确认下标合法再读取值。顺序反了就是越界访问。B4501 的 VLAint map[n][m]是变长数组VLA不是标准 C。GESP 考试环境可能支持但不是可移植写法。可用vectorvectorint或固定大小数组替代。B4501 的山谷定义是不高于——而非。两个等高相邻格子都可能是山谷。如果误用等高格子会被误判为非山谷。B4557 的行号转换题目说行号从 1 开始代码用x-1, y-1转为 0 基。如果忘了减 1雷会放错位置。B4557 的输出格式每个数字后跟空格每行末尾也有空格然后换行。漏空格或漏换行都会格式错误。 延伸扫雷的故事——从 1973 到今天你在 B4557 里写的八方向邻居检查不是一个抽象的算法练习——它是扫雷游戏的核心机制。每个非雷格子显示周围 8 个方向的雷数这正是你在代码里做的sum。而这个游戏有超过 50 年的故事。 前身1973-1985扫雷的基因可以追溯到 1970 年代的大型机时代Minesweeper History — cpscount.com年份游戏平台意义1973CubeJerimac Ratliff大型机已知最早的扫雷祖先Minesweeper History — minesweeperblast.com1983Mined-OutIan AndrewZX Spectrum第一个用数字提示周围雷数的游戏Mined-Out — HandWiki1985Relentless LogicTom AndersonMS-DOS确立了穿越雷场的现代扫雷机制Minesweeper Evolution — freetoplaypuzzles1987MineTom AndersonSunOS在 Sun 工作站上写的版本1988MineDaniel GrizzcomMacintosh基于 Anderson 1987 版本的 Mac 移植Mined-Out1983是第一个明确使用显示周围雷数机制的游戏玩家在网格中移动当前位置的数字告诉你周围有多少颗雷但不说具体在哪——需要玩家自己推理Mined-Out — HandWiki。你在 B4557 里计算的sum就是 Mined-Out 在 1983 年给玩家显示的那个数字。Relentless Logic1985加入了从一角穿越到对角的目标一个士兵要穿过雷场。每个揭示的格子显示周围雷数——和现代扫雷几乎一样Minesweeper Evolution — freetoplaypuzzles。 1989 年的学习项目1989 年微软工程师Curt Johnson被雇来维护 IBM OS/2 的调试器。为了自学 OS/2 的图形环境Presentation Manager他写了一个小程序叫“PM Mine”——以他在 Macintosh 上最喜欢的游戏 “Mine” 命名Minesweeper History — cpscount.com。当时微软的画图软件还是黑白的Johnson 甚至得先自己写一个彩色位图编辑器。PM Mine 和那个编辑器是他最早的程序之一。他的版本的目标是从左下角穿越雷场到右上角——保留了 Relentless Logic 的穿越机制。Johnson 把源代码分享给了同年入职的同事Robert DonnerMinesweeper History — cpscount.com。扫雷最初的形态是一个工程师为了学编程而写的练习项目。和你今天在洛谷上做题做的事本质上一样。 1990-1992从 Entertainment Pack 到 Windows 3.11990 年 5 月 22 日Windows 3.0 发布。Donner 把 PM Mine 重写为 Windows 版本改名“Win Mine”Minesweeper History — cpscount.com。1990 年 10 月 8 日微软发布Microsoft Entertainment Pack for Windows——7 个游戏加一个屏幕保护程序售价 $39.95。这是微软为 Windows 3.0 而非 MS-DOS 构建的第一批游戏。包装上的口号诚实地写着“Now you can use the incredible power of Windows 3.0 to goof off.”现在你可以用 Windows 3.0 的惊人性能来摸鱼了。扫雷是其中最受欢迎的游戏。Entertainment Pack 卖得太好微软又出了三个续包第一个被追溯命名为Entertainment Pack 1Minesweeper History — cpscount.com。1992 年扫雷被纳入Windows 3.1的标准安装取代了旧的 Reversi 游戏。从此扫雷出现在 1990 年代几乎每一台办公和家用 PC 上——一个点击之遥。三个经典难度沿用至今初级 9×9/10 雷、中级 16×16/40 雷、专家 16×30/99 雷Minesweeper History — cpscount.com。️ 教你用鼠标的设计意图Windows 3.1 时代很多人从没用过鼠标。扫雷和纸牌被设计成鼠标教学工具左键揭示格子、右键插旗——精确练习单击和右击Minesweeper History — minesweeper-online.com。游戏教的鼠标操作游戏机制纸牌Solitaire拖放drag-and-drop把牌拖到目标位置扫雷Minesweeper单击 右键左键揭示、右键标记你在 B4557 里写的if(grid[ni][nj] -1) sum曾经教会了 1990 年代几亿人怎么用鼠标。游戏里的数字不是给你看的——是给那些刚接触电脑的人一个理由去点击、去练习、去熟悉这个叫做鼠标的新工具。 1999-2001禁雷运动1999-2001 年间一个自称“International Campaign to Ban Winmine”国际禁雷运动的组织提出扫雷游戏对真正的地雷受害者不敏感建议把雷换成花朵。微软在一些本地化版本中确实发布了“Flower Field”花田皮肤作为回应Minesweeper History — cpscount.com。这是游戏文化可见度的一个脚注——一个捆绑的益智游戏能引起社会争议说明它已经不只是一个程序而是一个文化符号。 2012 至今离开默认安装活在到处扫雷随每一版 Windows 一直到 Windows 7Vista 和 7 版由 Oberon Media 重新开发。2012 年 Windows 8 发布时扫雷被移出默认安装转为 Microsoft Store 的免费下载Minesweeper History — cpscount.com。但扫雷没有消失。它散布到无数网页版、手机版、克隆版中。今天扫雷不再是一个单一程序而是计算文化中的永久存在——一个一分钟学会、一辈子深入的谜题。 八方向邻居检查从游戏到算法你在 B4501 和 B4557 里写的八方向遍历就是扫雷的核心机制。让我们把游戏和算法放在一起看扫雷游戏中的操作你的代码中的对应算法名称点击格子 → 显示周围雷数for dir in 8方向: if 邻居雷: sum邻居计数数字 0 → 自动展开周围递归/队列展开零区域洪水填充Flood Fill右键插旗 → 标记雷标记数组flag[i][j] true状态标记第一次点击安全生成雷时避开首次点击位置延迟生成B4557 做的是扫雷的数字生成——给定雷的位置计算每个格子的数字。真实扫雷游戏在玩家第一次点击后才生成雷保证第一次不踩雷生成方式和你写的代码一模一样。B4501 做的是找山谷——和扫雷的机制不同但用的同一种遍历。八方向邻居遍历不专属于扫雷但扫雷让它被全世界数十亿人熟知。你在洛谷上写的for(dir...)循环和 1989 年 Curt Johnson 在 OS/2 上写的 PM Mine 里的循环做的是同一件事——遍历八个方向检查邻居。区别只是Johnson 的结果画在屏幕上给你的鼠标点你的结果存在数组里给评测机判。 延伸阅读文献论文与技术文档E. F. Codd.A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 1970. —— 关系数据库的奠基论文网格数据的数学基础。J. H. Conway.On Numbers and Games. Academic Press, 1976. —— 组合博弈论网格游戏的数学理论。在线资源洛谷.B4501 [GESP202603 四级] 山之谷. https://www.luogu.com.cn/problem/B4501洛谷.B4557 [GESP202606 四级] 扫雷. https://www.luogu.com.cn/problem/B4557The History of Minesweeper: Mainframes, Windows and Logic Puzzles — cpscount.com. Minesweeper History —— 最详细的扫雷历史从 1973 到今天。Minesweeper History — minesweeperblast.com. Minesweeper History Timeline —— 扫雷时间线含 1973 Cube 到 2025 的完整年表。Mined-Out — HandWiki. Mined-Out — Wikipedia —— 1983 年 Ian Andrew 的 Mined-Out 百科条目。The Surprising Evolution of Minesweeper — freetoplaypuzzles. Minesweeper Evolution —— 从 Windows 3.1 到竞速社区的进化。History of Minesweeper — minesweeper-online.com. Minesweeper History —— Johnson 和 Donner 的开发故事含教你用鼠标的设计意图。A Boom of Nostalgia — hey.gg. Minesweeper Nostalgia —— 扫雷的完整谱系Relentless Logic → Mine(SunOS) → Mine(Mac) → PM Mine → Win Mine。推荐教材T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.Introduction to Algorithms(4th Edition). MIT Press, 2022. —— 含网格遍历、洪水填充等基础算法。R. Rucker.Software Engineering and Computer Games. McGraw-Hill, 2004. —— 从游戏角度讲解软件工程含网格游戏的设计。J. Schell.The Art of Game Design: A Book of Lenses(3rd Edition). CRC Press, 2019. —— 游戏设计经典含教学工具作为游戏设计目标。本文标签#算法 #八方向遍历 #邻居计数 #网格 #扫雷 #极值判定 #边界检查 #洛谷题解 #信奥 #C #GESP本文首发于CSDN作者HugoStudio_SWAN