当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

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

2020年04月15日  | 移动技术网IT编程  | 我要评论

吞食孔明传,fzlm,海娜花洗发水

该题目首先我想到的算法是bfs，但是bfs的空间复杂度较高，需要额外的队列，在看完题解之后，发现了动态规划这个好办法。具体程序代码如下：

vector<vector<int>> updatematrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] = int_max / 2;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i - 1 >= 0) {
                    matrix[i][j] = min(matrix[i][j], matrix[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    matrix[i][j] = min(matrix[i][j], matrix[i][j - 1] + 1);
                }
            }
        }

        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) {
                    matrix[i][j] = min(matrix[i][j], matrix[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    matrix[i][j] = min(matrix[i][j], matrix[i][j + 1] + 1);
                }
            }
        }
        
        return matrix;
    }

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网