542. 01矩阵

题目描述

给定一个由0和1组成的矩阵，找出每个元素到最近0的距离，相邻元素间的距离为1。
例如：
输入

0 0 0
0 1 0
0 0 0

输出

0 0 0
0 1 0
0 0 0

注意：

1. 给定矩阵的元素个数不超过 10000。
2. 给定矩阵中至少有一个元素是 0。
3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解题思路

广度优先搜索。
首先遍历找到元素0的位置。从该位置进行4个方向的广度遍历，更新4个方向元素的距离，然后加入元素0队列，如此继续遍历。示意图如下：

_ _ _ _         _ 1 _ _         2 1 2 _         2 1 2 3         2 1 2 3
_ 0 _ _   ==>   1 0 1 _   ==>   1 0 1 2   ==>   1 0 1 2   ==>   1 0 1 2
_ _ _ _         _ 1 _ _         2 1 2 _         2 1 2 3         2 1 2 3
_ _ _ _         _ _ _ _         _ 2 _ _         3 2 3 _         3 2 3 4

代码

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    q.emplace(i, j);
                    seen[i][j] = 1;
                }
            }
        }

        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // 广度优先搜索
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }

        return dist;

    }
};

复杂度分析

• 时间复杂度：O(rc)，其中r为矩阵行数，c为矩阵列数
• 空间复杂度：O(rc)