LeetCode 529. Minesweeper 扫雷游戏题解LeetCode-Go 项目中的 DFS 递归展开实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 LeetCode 529. Minesweeper 的题解文档为主体完整讲解扫雷棋盘的状态模型、四条点击规则与两个官方示例并深入 529. Minesweeper.go 源码剖析其基于八方向dir8数组的深度优先搜索DFS递归展开实现包括边界判断、数字编码技巧与递归守卫条件背后的不变式。读完本文你将掌握这类点击展开 图遍历题型的标准解法框架并能用 BFS 思路自行改写验证。一、题目回顾扫雷棋盘的状态模型LeetCode 529 要求我们实现扫雷游戏的一次点击行为。给定一个代表游戏棋盘的二维字符矩阵board其中每个格子只可能是以下六种状态之一字符含义M未挖出的地雷unrevealed mineE未挖出的空方块unrevealed empty squareB已挖出的空白方块周围上、下、左、右以及全部 4 条对角线共 8 个方向没有地雷1~8已挖出的方块数字表示其周围相邻地雷的数量X已挖出的地雷踩雷游戏结束输入还会给出一个点击坐标click行列索引且该位置必然是未挖出的方块M或E。根据以下四条规则更新棋盘并返回踩雷如果挖出的是地雷M游戏结束将其改为X空白递归展开如果挖出的是空方块E且周围 8 个方向都没有地雷则改为B并递归地揭露其所有相邻的未挖出方块数字标注如果挖出的是空方块E且周围至少有一个地雷则改为数字1~8表示相邻地雷数量当没有更多方块需要被揭露时返回棋盘。题目在 Note 中给出的输入约束这些约束也是实现时可以依赖的前提输入矩阵的高度和宽度范围为[1, 50]点击位置只会是未挖出的方块M或E即面板至少包含一个可点击方块输入面板不会是游戏已结束的状态不存在已挖出的地雷简单起见未提及的规则可以忽略例如游戏结束时不要求展开所有剩余地雷也不需要考虑标记旗帜、判定胜利等场景。二、官方示例推演从输入到输出示例 1点击空白触发递归展开输入棋盘 [[E, E, E, E, E], [E, E, M, E, E], [E, E, E, E, E], [E, E, E, E, E]] 点击坐标[3, 0]左下角 输出棋盘 [[B, 1, E, 1, B], [B, 1, M, 1, B], [B, 1, 1, 1, B], [B, B, B, B, B]]推演过程点击(3,0)是E其周围 8 个方向没有任何地雷因此改为B并递归展开邻居。(2,0)、(3,1)同样周围无雷变为B并继续展开而(2,1)、(1,0)、(1,1)等格子距离(1,2)的地雷只有一步周围能数出 1 颗雷因此标为1。(0,0)、(0,4)与(0,1)、(0,3)之间的格子在展开中因邻居链而触及最终形成 B/1 环绕 E 的典型边界形态。注意(1,2)的M与(0,2)、(2,2)的E保持原样——它们与空白区之间隔着数字格不会被递归触及。示例 2点击地雷游戏结束输入棋盘 [[B, 1, E, 1, B], [B, 1, M, 1, B], [B, 1, 1, 1, B], [B, B, B, B, B]] 点击坐标[1, 2]地雷位置 输出棋盘 [[B, 1, E, 1, B], [B, 1, X, 1, B], [B, 1, 1, 1, B], [B, B, B, B, B]]推演过程该棋盘是示例 1 的输出状态点击(1,2)时该位置是M命中规则 1直接改为X并返回其余格子全部保持不变。这一示例同时验证了输入面板不会是游戏结束状态的前提——示例 1 的输出来自未踩雷的点击所以可以作为示例 2 的合法输入。三、解题思路DFS 与 BFS 皆可的图遍历问题原文档的解题思路明确指出DFS 和 BFS 都可以解题文档原文写作DPS应为 DFS。这道题的本质是模拟 图遍历棋盘可以看作一张网格图每个格子是节点与周围 8 个格子相邻规则 2 的递归揭露相邻未挖出方块就是一次从点击点出发的遍历规则 3 是遍历的终止条件一旦遇到周围有雷的格子就只标注数字、不再向下展开。LeetCode-Go 仓库选择的是DFS 递归实现完整源码位于 leetcode/0529.Minesweeper/529. Minesweeper.go。该文件最值得注意的是全局八方向数组var dir8 [][]int{ {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, }dir8从左上角开始顺时针枚举 8 个方向上左、上、上右、右、下右、下、下左、左。与题目要求的上、下、左、右和所有 4 条对角线完全对应。用方向数组而不是手写 8 个分支能让遍历代码保持简洁且不易遗漏方向。关于原文档提到的预处理思路可以这样理解先离线统计出每个格子最终的状态0 代表空白砖块、1~8 代表雷的个数、-1 代表雷再在预处理后的图上遍历输出。不过仓库最终给出的代码采用了更省空间的就地in-placeDFS方案不额外建图直接在board上一边判定一边改写本质上实现了同样的效果。复杂度分析时间复杂度最坏情况下整个棋盘被递归展开一遍每个格子最多被访问一次数字格可能被相邻空白格重复进入但每次仅做 O(8) 的计数后即返回次数受邻接度限制总体为 O(R × C)其中 R、C 分别为棋盘行数和列数空间复杂度递归栈最深可达棋盘大小最坏为 O(R × C)若不考虑递归栈则只用了常数额外空间。四、源码精读updateBoard 与 dfs 的协作LeetCode-Go 的实现只有三个函数入口updateBoard、递归dfs和边界检查isInBoard逻辑分层非常清晰。1. 入口函数处理踩雷分支func updateBoard(board [][]byte, click []int) [][]byte { if board[click[0]][click[1]] M { board[click[0]][click[1]] X return board } dfs(board, click[0], click[1]) return board }入口函数对应规则 1如果点击位置是M直接改为X并返回对应示例 2。否则说明点击的是E进入dfs做递归展开。注意这里利用了题目的约束——点击位置必然是未挖出的格子因此无需再判断E之外的情况。2. 递归函数计数 → 标注 → 展开func dfs(board [][]byte, x, y int) { cnt : 0 for i : 0; i 8; i { nx, ny : xdir8[i][0], ydir8[i][1] if isInBoard(board, nx, ny) board[nx][ny] M { cnt } } if cnt 0 { board[x][y] byte(cnt 0) return } board[x][y] B for i : 0; i 8; i { nx, ny : xdir8[i][0], ydir8[i][1] if isInBoard(board, nx, ny) board[nx][ny] ! B { dfs(board, nx, ny) } } }这段代码是核心拆开看有三步第一步统计周围地雷数。遍历dir8的 8 个方向先经isInBoard做越界检查再判断邻居是否为M累加到cnt。这一步对应规则 2、3 的判定前提。第二步依据计数决定当前格状态。若cnt 0把当前格改为数字byte(cnt 0)并return——这是一个经典的字符编码技巧0的 ASCII 码是 48cnt 0恰好把整数 1~8 转换为字符1~8无需strconv或类型转换函数。对应规则 3。若cnt 0改为B对应规则 2 的前半句。第三步递归展开邻居。仅当当前格是B即周围无雷时才遍历 8 个邻居递归调用dfs对应规则 2 的后半句。这里的守卫条件是board[nx][ny] ! B它隐含一个值得注意的不变式递归展开只会发生在周围无雷的格子身上因此它的 8 个邻居里不可能有M否则计数不会为 0所以dfs永远不会把地雷M改写掉同时被标注过数字的邻居即使被再次进入也只是重复计算相同的cnt并重新写入同样的数字结果幂等不会破坏棋盘。这一设计使得实现无需额外的 visited 标记数组仅靠棋盘自身状态即可防重复展开空间开销更小。3. 边界检查func isInBoard(board [][]byte, x, y int) bool { return x 0 x len(board) y 0 y len(board[0]) }isInBoard统一收口所有越界判断行号x必须在[0, len(board))列号y必须在[0, len(board[0]))。由于题目保证棋盘宽高都在[1, 50]范围内这里无需处理空棋盘。完整调用链一次点击的完整链路为updateBoard(board, click) └─ 点击是 M ? → 改为 X返回 └─ 点击是 E → dfs(board, x, y) ├─ 统计 8 方向地雷数 cnt ├─ cnt 0 → 写数字返回 └─ cnt 0 → 写 B递归 8 个邻居isInBoard 非 B 守卫五、测试验证从测试文件与项目脚本看正确性LeetCode-Go 为每一题都配套了表驱动风格的测试用例本题的测试位于 leetcode/0529.Minesweeper/529. Minesweeper_test.go。测试文件的核心结构是question529结构体包含参数para529棋盘b与点击坐标click和期望答案ans529输出棋盘one这与仓库中其他题目的测试风格完全一致type question529 struct { para529 ans529 } type para529 struct { b [][]byte click []int } type ans529 struct { one [][]byte }Test_Problem529中注册了两个用例恰好与本文第二节的两个官方示例一一对应用例一输入示例 1 的 4×5 棋盘与点击[3, 0]期望输出示例 1 的结果用例二输入示例 2 的棋盘与点击[1, 2]期望输出示例 2 的结果。测试函数通过fmt.Printf打印每个用例的输入与输出便于在go test -v时人工核对。运行整个仓库测试的方式可以参考项目根目录的 gotest.sh 脚本它使用 Go 1.10 的单次覆盖文件写法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该命令会以atomic覆盖模式对leetcode包树下所有题目执行测试并生成 coverage.txt 覆盖率文件这正是仓库100% test coverage工程实践的落地方式。项目模块名为github.com/halfrost/LeetCode-GoGo 版本要求 1.19详见 go.mod。六、总结与延伸思考本题本质LeetCode 529 是模拟 图遍历的典型代表棋盘即图dir8定义邻接关系规则 2 是遍历展开规则 3 是遍历终止条件规则 1 是输入特判。LeetCode-Go 用约 30 行 Go 代码完成了从入口判断、递归展开到边界检查的全部逻辑其dir8 就地改写 无 visited 数组的组合值得在同类网格遍历题如岛屿类问题中复用。延伸一BFS 版本如何写原文档指出 BFS 同样可解。BFS 只需把dfs的递归改为队列初始将点击点入队出队时统计周围地雷数若cnt 0写数字否则写B并把 8 个邻居中未被处理的格子入队。由于需要防止重复入队BFS 版本通常需要额外的 visited 标记这是 DFS 就地改写方案的一个优势。延伸二可变式变体可以进一步思考如果题目要求在踩雷后把所有未展开的地雷都显示为X真实的扫雷游戏失败表现只需在规则 1 分支中追加一次全盘扫描把每个M改为X如果要求支持旗帜标记则需要在dfs的守卫条件中额外排除已被标记的格子。理解当前实现的递归不变式之后这些扩展都能在保持结构不变的前提下快速完成。延伸三相邻题型的横向对比仓库中还收录了若干与网格 方向遍历强相关的题目可作对比阅读200. Number of Islands四方向连通分量计数、695. Max-Area-of-Island四方向区域面积、130. Surrounded-Regions边界逆向填充。它们的差异点在于岛屿题只有0/1两种状态且只向四方向扩展而本题有六种状态、八方向扩展并且多了一道数字格充当防火墙的终止逻辑——这正是本题区别于普通连通分量题的核心考点。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考