0542. 01 Matrix

题目信息

题号:

0542

难度:

Medium

主题:

二进制矩阵、最近零、四方向距离、结果矩阵

原题:

LeetCode 0542

重点:

距离按上下左右移动次数计算、每个格子独立寻找最近的 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)。