跳转至

01 矩阵 (Medium)*

题目描述*

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

注意*

给定矩阵的元素个数不超过 10000。

给定矩阵中至少有一个元素是 0。

矩阵中的元素只在四个方向上相邻: 上、下、左、右。

代码*

最简单的思路从每个 1 开始用 bfs，找到最近的 0。但这样每次只能更新一个点，如果从 0 出发 bfs，可提升效率。

或者使用动态规划，先从左上到右下，再从右下到左上。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        if(rows == 0) {
            return matrix;
        }
        int cols = matrix[0].size();
        vector<vector<int>> res(rows, vector<int>(cols, INT_MAX));
        queue<pair<int, int>> q;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(matrix[i][j] == 0) {
                    res[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while(!q.empty()) {
            auto cur = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) {
                int x = cur.first + dirs[i].first, y = cur.second + dirs[i].second;
                if(x >= 0 && y >= 0 && x < rows & y < cols) {
                    if(res[x][y] > res[cur.first][cur.second] + 1) {
                        res[x][y] = res[cur.first][cur.second] + 1;
                        q.push({x, y});
                    }
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[0].size(); j++) {
                if(matrix[i][j] == 0) {
                    continue;
                }
                int i_1, j_1;
                if(i != 0) {
                    i_1 = dp[i - 1][j] + 1;
                }else {
                    i_1 = 10000;
                }
                if(j != 0){
                    j_1 = dp[i][j - 1] + 1;
                }else {
                    j_1 = 10000;
                }
                dp[i][j] = (i_1 >= j_1) ? j_1 : i_1;
            }
        }
        for(int i = matrix.size() - 1; i >= 0; i--) {
            for(int j = matrix[0].size() - 1; j >= 0; j--) {
                if(matrix[i][j] == 0) {
                    continue;
                }
                int i_1, j_1;
                if(i != matrix.size() - 1) {
                    i_1 = dp[i + 1][j] + 1;
                }else {
                    i_1 = 10000;
                }
                if(j != matrix[0].size() - 1) {
                    j_1 = dp[i][j + 1] + 1;
                }else {
                    j_1 = 10000;
                }
                dp[i][j] = min(dp[i][j], min(i_1, j_1));
            }
        }
        return dp;
    }
};
最后更新: July 23, 2022