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 部分）：

1. 矩阵的元素总数不超过 10,000；
2. 矩阵中至少存在一个 0（保证答案总是存在）；
3. 单元格只在上下左右四个方向上相邻。

原文档的「题目大意」把问题凝练为一句话：给定一个只含 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 }

要点说明：

1. 多源初始化：一次双重循环把所有0写入结果矩阵为-1并压入队列。-1有两个作用：标记「这是源点格子，答案最终要还原成 0」；同时充当 BFS 的「已访问」标记，防止源点被波纹再次污染。
2. 按层扩散：外层循环每轮取出当前层的全部节点（size := len(queue)固定当前层数量），内层循环逐个出队，再对四个方向{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}扩展。每处理完一整层，level++，层数正好等于该波格子的最短距离。
3. 跳过条件：越界、res[x][y] < 0（是源点或已被访问）、res[x][y] > 0（已被更早的波纹赋值）三种情况一律continue。这里的> 0判断正是「第一次到达即为最短」的实现——更晚到达的波纹不会覆盖已有答案。
4. 收尾还原：遍历结果矩阵，把-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[row+1][col] == 0 { return true } if col < len(matrix[0])-1 && matrix[row][col+1] == 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, row+1, col, matrix[row][col]+1) dfsMatrix(matrix, row, col+1, matrix[row][col]+1) }

要点说明：

1. 剪枝条件：越界，或matrix[row][col] <= val（当前格子的已有距离已经不大于将要写入的值），立即返回。因为 DFS 是深度优先，后到达的路径可能更长，只有更短的步数才有更新价值。
2. 初始调用：对每个原始为 1 的格子调用dfsMatrix(matrix, r, c, -1)。val = -1不满足val > 0，不会把 1 覆盖成负数，仅作为递归的「起跳值」。
3. 步数累加：向四个方向递归时传入matrix[row][col]+1，距离逐层 +1，与「相邻格子距离为 1」的定义一致。
4. 原地修改：该解法直接改写输入的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[i+1][j] + 1 } if j < len(matrix[0])-1 { right = matrix[i][j+1] + 1 } matrix[i][j] = min(matrix[i][j], min(bottom, right)) } } return matrix }

要点说明：

1. 正向扫描：遇到0直接跳过（答案为 0）；对1，若上方存在则候选top = matrix[i-1][j] + 1，若左方存在则候选left = matrix[i][j-1] + 1，取两者较小值。边界格子没有上/左邻居时用math.MaxInt16占位，保证min不会误选到无效方向。
2. 反向扫描：从右下角向左上角推进，候选为bottom = matrix[i+1][j] + 1与right = matrix[i][j+1] + 1，与当前值取min。这里必须用min(matrix[i][j], min(bottom, right))，保留第一轮已经算出的「上/左方向」结果，形成四个方向的完整覆盖。
3. 原地递推：直接修改输入的matrix并返回，额外空间 O(1)（不计入输入矩阵本身），是本解法的最大优势。
4. 仓库自带的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报错——相当于三种算法互相印证、对拍验证。

测试用例覆盖了四种典型场景：

1. 空矩阵：[][]int{}，验证空输入边界；
2. 示例 1：3×3 中心一个 1 的矩阵；
3. 示例 2：3×3 中「L 形」分布的 1；
4. 6×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 -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），配合已有的 coverage.txt，印证了本仓库「LeetCode 题解 + 100% 测试覆盖」的工程化目标。

三种解法对比与选型建议

实战选型建议：

• 追求最稳、最不易错：多源 BFS。它在无权图上天然保证最短性，语义与题目「距离最近」完全对应；
• 追求原地省内存：两次遍历 DP，O(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