0542. 01 Matrix =============== 题目信息 -------- :题号: 0542 :难度: Medium :主题: 二进制矩阵、最近零、四方向距离、结果矩阵 :原题: `LeetCode 0542 `_ :重点: 距离按上下左右移动次数计算、每个格子独立寻找最近的 0、题目保证至少存在一个 0 题目重述 -------- 给定一个只包含 ``0`` 和 ``1`` 的矩阵 ``mat``,返回一个同样大小的矩阵,其中结果位置 ``[i][j]`` 表示从原矩阵格子 ``[i][j]`` 到最近的 ``0`` 所需的最少移动步数。 每一步只能移动到上下左右相邻格子,不能沿对角线移动。原本为 ``0`` 的格子距离为 ``0``;题目保证矩阵中至少存在一个 ``0``,因此每个位置都有有限答案。 自建示例 -------- 只有一个零位于角落: .. code-block:: text 输入:mat = [[0,1,1],[1,1,1]] 输出:[[0,1,2],[1,2,3]] 解释:每个格子的答案等于它通过四方向移动到左上角零格的最短距离。 全部为零: .. code-block:: text 输入:mat = [[0,0],[0,0]] 输出:[[0,0],[0,0]] 解释:每个位置自身就是零格。 从所有零格同时开始 BFS ---------------------- 把所有值为 0 的格子一次性加入队列,距离设为 0;值为 1 的格子设为未访问。多源 BFS 按距离层扩展,某个格子第一次被访问时,必然是从最近的零格到达,因此可直接确定最短距离。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector> updateMatrix( std::vector>& mat) { int rows = static_cast(mat.size()); int columns = static_cast(mat[0].size()); std::queue> queue; std::vector> distance( rows, std::vector(columns, -1)); for (int row = 0; row < rows; ++row) { for (int column = 0; column < columns; ++column) { if (mat[row][column] == 0) { distance[row][column] = 0; queue.push({row, column}); } } } const int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; while (!queue.empty()) { auto [row, column] = queue.front(); queue.pop(); for (const auto& direction : directions) { int nextRow = row + direction[0]; int nextColumn = column + direction[1]; if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || distance[nextRow][nextColumn] != -1) continue; distance[nextRow][nextColumn] = distance[row][column] + 1; queue.push({nextRow, nextColumn}); } } return distance; } }; 代码分析 -------- 所有源点同层入队,BFS 的层数就是到最近源点的四方向距离,访问标记保证每格只被确定一次。时间复杂度为 ``O(rows * columns)``,队列和结果矩阵空间复杂度为 ``O(rows * columns)``。