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)``。