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