欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-25 16:26:36
该题目首先我想到的算法是bfs,但是bfs的空间复杂度较高,需要额外的队列,在看完题解之后,发现了动态规划这个好办法。具体程序代码如下: vector> updateMatrix(vector>& matrix) { int m = matrix.si ......

该题目首先我想到的算法是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;
    }