LeetCode-Go 题解：542. 01 Matrix 三种解法（BFS / DFS / DP）求解最近 0 距离

LeetCode-Go 题解542. 01 Matrix 三种解法BFS / DFS / DP求解最近 0 距离【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 leetcode/0542.01-Matrix/README.md 为主线结合仓库内的 核心实现 与 测试用例完整剖析 LeetCode 542「01 矩阵」这道经典的多源最短距离问题。读完本文你将掌握为什么这类「求每个格子到最近 0 的距离」的问题可以用多源 BFS 一次求解如何用 DFS 加剪枝完成同样的任务以及如何用两次遍历的动态规划做到 O(R×C) 时间、O(1) 额外空间并看懂仓库中三种解法并存、对拍验证的工程化写法。题目回顾给每个 1 找到最近的 0给定一个仅由0和1组成的矩阵要求为矩阵中的每一个单元格计算它到最近的 0的曼哈顿距离两个相邻单元格之间的距离为 1。四个方向上、下、左、右上的移动才被允许。示例 1输入 [[0,0,0], [0,1,0], [0,0,0]] 输出 [[0,0,0], [0,1,0], [0,0,0]]示例 2输入 [[0,0,0], [0,1,0], [1,1,1]] 输出 [[0,0,0], [0,1,0], [1,2,1]]题目约束来自原文档 Note 部分矩阵的元素总数不超过 10,000矩阵中至少存在一个 0保证答案总是存在单元格只在上下左右四个方向上相邻。原文档的「题目大意」把问题凝练为一句话给定一个只含 0 和 1 的二维数组计算每个 1 距离最近的 0 的距离。0格子的答案恒为 0只有1格子需要求解。解题思路总览一条题目的三条经典路线原文档明确指出这一题有 3 种解法且给出了各自的策略方向BFS多源广度优先搜索最直观。把所有 0 作为「水源」一次性入队让波纹一层层向外扩散第一次扫到某个 1 时得到的层数就是最短距离DFS深度优先 剪枝先做预处理再递归地向四周扩散用「已有值更小就不再更新」的剪枝保证正确性DP两次遍历动态规划把四个方向拆成「上 左」与「下 右」两轮扫描利用最优子结构原地递推。三种解法在仓库 542. 01 Matrix.go 中分别对应updateMatrixBFS、updateMatrixDFS、updateMatrixDP三个函数下面逐一拆解。解法一多源 BFS「石头扔进湖里」的波纹扩散思路与预处理BFS 的思路来自「离它最近的 0」这一语义如果从每个 0 同时出发向四周扩散那么某个 1 被哪一波波纹最先触及它离 0 的距离就是那波的层数。原文档用了一个非常形象的比喻像一颗石头扔进湖里一圈一圈的波纹荡开每一圈都是一层。关键预处理技巧把所有值为0的格子标记为-1并入队作为 BFS 的多源起点值为1的格子保持为0等待波纹扫过时被赋上「层数」。由于-1只属于原始为 0 的格子波纹扩散时无需再处理它们它们本身就是源点答案为 0而所有值为0的格子都是原始为 1 的格子第一次被波纹扫到时立刻赋值更新。之后即使波纹再次扫到因为它已经有值了直接跳过——第一次到达的一定是最短距离这也是 BFS 在无权图上保证最短路的根本原因。源码逐段分析// 解法一 BFS func updateMatrixBFS(matrix [][]int) [][]int { res : make([][]int, len(matrix)) if len(matrix) 0 || len(matrix[0]) 0 { return res } queue : make([][]int, 0) for i : range matrix { res[i] make([]int, len(matrix[0])) for j : range res[i] { if matrix[i][j] 0 { res[i][j] -1 queue append(queue, []int{i, j}) } } } level : 1 for len(queue) 0 { size : len(queue) for size 0 { size-- node : queue[0] queue queue[1:] i, j : node[0], node[1] for _, direction : range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} { x : i direction[0] y : j direction[1] if x 0 || x len(matrix) || y 0 || y len(matrix[0]) || res[x][y] 0 || res[x][y] 0 { continue } res[x][y] level queue append(queue, []int{x, y}) } } level } for i, row : range res { for j, cell : range row { if cell -1 { res[i][j] 0 } } } return res }要点说明多源初始化一次双重循环把所有0写入结果矩阵为-1并压入队列。-1有两个作用标记「这是源点格子答案最终要还原成 0」同时充当 BFS 的「已访问」标记防止源点被波纹再次污染。按层扩散外层循环每轮取出当前层的全部节点size : len(queue)固定当前层数量内层循环逐个出队再对四个方向{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}扩展。每处理完一整层level层数正好等于该波格子的最短距离。跳过条件越界、res[x][y] 0是源点或已被访问、res[x][y] 0已被更早的波纹赋值三种情况一律continue。这里的 0判断正是「第一次到达即为最短」的实现——更晚到达的波纹不会覆盖已有答案。收尾还原遍历结果矩阵把-1全部还原为0。复杂度设矩阵为 R 行 C 列。时间上每个格子最多入队出队一次为 O(R×C)空间上结果矩阵 O(R×C)队列最坏情况下例如全 0 矩阵也接近 O(R×C)。解法二DFS 剪枝把「没邻居的 1」先抬到无穷大思路与预处理BFS 是从 0 向外推DFS 则是反过来从 1 向内递归。原文档给出了这一解法的核心洞察先预处理把「四周没有 0 的 1」重置为最大值四周有 0 的 1它们到 0 的距离就是 1这些点不需要移动真正需要更新的是那些周围没有 0的点递归时只要当前步数val比格子上的值更小就不断更新它——这就是为什么要先把某些格子抬到最大值让它们可以被任意更小的步数覆盖。源码逐段分析// 解法二 DFS func updateMatrixDFS(matrix [][]int) [][]int { result : [][]int{} if len(matrix) 0 || len(matrix[0]) 0 { return result } maxRow, maxCol : len(matrix), len(matrix[0]) for r : 0; r maxRow; r { for c : 0; c maxCol; c { if matrix[r][c] 1 hasZero(matrix, r, c) false { // 将四周没有 0 的 1 特殊处理为最大值 matrix[r][c] math.MaxInt64 } } } for r : 0; r maxRow; r { for c : 0; c maxCol; c { if matrix[r][c] 1 { dfsMatrix(matrix, r, c, -1) } } } return (matrix) }hasZero负责判断某格子的上下左右四个邻居中是否存在0存在则说明该格子答案就是 1无需参与递归// 判断四周是否有 0 func hasZero(matrix [][]int, row, col int) bool { if row 0 matrix[row-1][col] 0 { return true } if col 0 matrix[row][col-1] 0 { return true } if row len(matrix)-1 matrix[row1][col] 0 { return true } if col len(matrix[0])-1 matrix[row][col1] 0 { return true } return false }递归函数dfsMatrix是核心func dfsMatrix(matrix [][]int, row, col, val int) { // 不超过棋盘范围且 val 要比 matrix[row][col] 小 if row 0 || row len(matrix) || col 0 || col len(matrix[0]) || (matrix[row][col] val) { return } if val 0 { matrix[row][col] val } dfsMatrix(matrix, row-1, col, matrix[row][col]1) dfsMatrix(matrix, row, col-1, matrix[row][col]1) dfsMatrix(matrix, row1, col, matrix[row][col]1) dfsMatrix(matrix, row, col1, matrix[row][col]1) }要点说明剪枝条件越界或matrix[row][col] val当前格子的已有距离已经不大于将要写入的值立即返回。因为 DFS 是深度优先后到达的路径可能更长只有更短的步数才有更新价值。初始调用对每个原始为 1 的格子调用dfsMatrix(matrix, r, c, -1)。val -1不满足val 0不会把 1 覆盖成负数仅作为递归的「起跳值」。步数累加向四个方向递归时传入matrix[row][col]1距离逐层 1与「相邻格子距离为 1」的定义一致。原地修改该解法直接改写输入的matrix并返回它因此调用方需要深拷贝输入测试文件中的clone542就是为此准备的。复杂度预处理需要 O(R×C)递归阶段因为有「已有更小值则不再更新」的剪枝每个格子的更新次数有限从源码结构看整体接近 O(R×C) 量级递归调用栈最深为 O(R×C)例如全 1 单连通区域。与原文档表述一致DFS 的定位是「容易想到、便于理解」的替代方案实际工程中多源 BFS 或 DP 更可控。解法三两次遍历 DP四方向拆成两轮扫描思路DP 解法的巧妙之处在于对方向的拆分。一个格子的最短距离可能来自四个方向但如果一次只看两个方向就可以用经典的「正向 反向」两遍扫描完成第一遍从上到下、从左到右遍历先处理「上边」和「左边」两个方向第二遍从下到上、从右到左遍历再处理「右边」和「下边」两个方向。两轮取最小值之后四个方向都被覆盖正确性由「子问题的最优解 当前步长」的递推保证。原文档特别指出这种方式可以降低时间复杂度——相较于朴素的四方向重复更新两次线性扫描只需 O(R×C)。源码逐段分析// 解法三 DP func updateMatrixDP(matrix [][]int) [][]int { for i, row : range matrix { for j, val : range row { if val 0 { continue } left, top : math.MaxInt16, math.MaxInt16 if i 0 { top matrix[i-1][j] 1 } if j 0 { left matrix[i][j-1] 1 } matrix[i][j] min(top, left) } } for i : len(matrix) - 1; i 0; i-- { for j : len(matrix[0]) - 1; j 0; j-- { if matrix[i][j] 0 { continue } right, bottom : math.MaxInt16, math.MaxInt16 if i len(matrix)-1 { bottom matrix[i1][j] 1 } if j len(matrix[0])-1 { right matrix[i][j1] 1 } matrix[i][j] min(matrix[i][j], min(bottom, right)) } } return matrix }要点说明正向扫描遇到0直接跳过答案为 0对1若上方存在则候选top matrix[i-1][j] 1若左方存在则候选left matrix[i][j-1] 1取两者较小值。边界格子没有上/左邻居时用math.MaxInt16占位保证min不会误选到无效方向。反向扫描从右下角向左上角推进候选为bottom matrix[i1][j] 1与right matrix[i][j1] 1与当前值取min。这里必须用min(matrix[i][j], min(bottom, right))保留第一轮已经算出的「上/左方向」结果形成四个方向的完整覆盖。原地递推直接修改输入的matrix并返回额外空间 O(1)不计入输入矩阵本身是本解法的最大优势。仓库自带的min辅助函数542. 01 Matrix.go 末尾实现了两数取小供 DP 使用。复杂度两轮遍历各 O(R×C)合计 O(R×C)空间 O(1)原地三解中效率最优。测试验证三种解法对拍 深拷贝隔离仓库为本题准备了专门的测试文件 542. 01 Matrix_test.go结构上遵循了本仓库统一的「表驱动 结构体分组」风格para542封装输入矩阵ans542封装期望输出组合成question542测试用例列表clone542负责深拷贝输入矩阵因为 DFS 和 DP 解法都是原地修改输入的若不拷贝前一个解法会污染后一个解法的输入Test_Problem542对同一组输入依次调用updateMatrixDP、updateMatrixBFS、updateMatrixDFS用reflect.DeepEqual与期望答案比对任何一个解法失败都会t.Fatalf报错——相当于三种算法互相印证、对拍验证。测试用例覆盖了四种典型场景空矩阵[][]int{}验证空输入边界示例 13×3 中心一个 1 的矩阵示例 23×3 中「L 形」分布的 16×6 中心块全 0 矩阵[[1,1,1,1,1,1], ...]中心 2×2 为 0答案呈对称的「同心方框」结构外圈 4、次圈 3、内圈 2/1用于检验算法在大一些的棋盘上、多个 0 同时存在时仍正确。在仓库根目录可以直接运行本题的测试go test ./leetcode/0542.01-Matrix/ -v-v会打印每个用例如【input】:... 【output】:...的调试信息。仓库根目录的 gotest.sh 还给出了对整个./leetcode/...包树生成覆盖率文件的写法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...配合已有的 coverage.txt印证了本仓库「LeetCode 题解 100% 测试覆盖」的工程化目标。三种解法对比与选型建议解法核心策略时间复杂度额外空间实现位置多源 BFS所有 0 入队波纹按层扩散首次到达即最短O(R×C)O(R×C)结果矩阵 队列updateMatrixBFSDFS 剪枝预处理孤立 1 为最大值递归更新更小步数接近 O(R×C)有剪枝最坏栈深 O(R×C)O(R×C)递归栈updateMatrixDFS/dfsMatrix/hasZero两次遍历 DP上/左一轮、下/右一轮原地取 minO(R×C)O(1)原地updateMatrixDP实战选型建议追求最稳、最不易错多源 BFS。它在无权图上天然保证最短性语义与题目「距离最近」完全对应追求原地省内存两次遍历 DPO(1) 额外空间且代码量不大但需要理解「两方向一轮」的拆分逻辑作为面试拓展DFS 解法体现「预处理 剪枝」的思维但需注意原地修改与递归深度问题。无论选择哪条路线都可以用仓库中的 测试用例 直接验证正确性。这一题的价值在于同一个问题用搜索BFS/DFS和动态规划DP两种不同的算法范式都能优雅解决是理解「多源最短路」「剪枝」「方向拆分递推」三种思想的绝佳载体。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考