3112、访问消失节点的最小时间

542、01 矩阵

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

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

示例 1:

输入:

0 0 0
0 1 0
0 0 0
输出:

0 0 0
0 1 0
0 0 0

示例 2:

输入:

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1

注意:

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

链接：https://leetcode-cn.com/problems/01-matrix

题解

• 对于(i,j)进行上下左右，四连通域的广义优先搜索。

1、广度优先搜索

题目中中的意思是：

对于矩阵中的所有的1，找到并计算与其最近的0的距离。反过来就是：对于每个0，更新周围1的距离使其最小。

C++实现

class Solution {
private:
    // 位移矩阵
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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;// 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]) {
                    // 新位置的距离在旧位置之上+1
                    dist[ni][nj] = dist[i][j] + 1;
                    // 新元素入队列
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }

    return dist;
    }
};

// 链接：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/

java实现

class Solution {
    class Point {
        int i,j;
        public Point(int x,int y) {
            this.i = x;
            this.j = y;
        }
    }
    int[][] dirs = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] res = new int[m][n];
        int[][] seen = new int[m][n];

        Queue<Point> queue = new LinkedList<>();

        for (int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                if (matrix[i][j] == 0){
                    queue.offer(new Point(i,j));
                    seen[i][j] = 1;
                }
            }
        }

        while(!queue.isEmpty()) {
            Point p = queue.peek();
            queue.poll();
            for(int k = 0;k < 4;k++) {
                int ni = p.i + dirs[k][0];
                int nj = p.j + dirs[k][1];
                if (ni >=0 && ni < m && nj >= 0 && nj < n && seen[ni][nj] == 0) {
                    res[ni][nj] = res[p.i][p.j] + 1;
                    queue.offer(new Point(ni,nj));
                    seen[ni][nj] = 1;
                }
            }
        }
        return res;
    }
}

2、动态规划

按照正常思维：

如果一个1周围是四个1，那么这个1与附近最近的0的距离为：

dist[i][j] = min(dist[i - 1][j],dist[i][j - 1],dist[i + 1][j],dist[i][j + 1]) + 1

否则：dist[i][j] = 1

###c++ 实现

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, INT_MAX / 2));
        // 如果 (i, j) 的元素为 0，那么距离为 0
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                if (i + 1 < m) {
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) {
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        return dist;
    }
};

// 链接：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/

Java实现

class Solution {
    public int[][] updateMatrix(int[][] matrix){
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dist = new int[m][n];
        // 初始化数组
        for(int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                if (matrix[i][j] == 1){
                    dist[i][j] = Integer.MAX_VALUE/2;
                }
            }
        }

        // 从左上遍历到右下，更新数组
        for(int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                // 左边的
                if (i > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i - 1][j]+1);
                }
                // 右边的
                if (j > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i][j - 1]+1);
                }
            }
        }
        // 从左下到右上更新数组
        for(int i = m-1;i >= 0;i--) {
            for (int j = 0;j < n;j++) {
                // 左边的
                if (i > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i + 1][j]+1);
                }
                // 右边的
                if (j > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i][j - 1]+1);
                }
            }
        }
        // 从右上到左下更新数组
        for(int i = 0;i < m;i++) {
            for (int j = n - 1;j >= 0;j--) {
                // 左边的
                if (i > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i - 1][j]+1);
                }
                // 右边的
                if (j > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i][j + 1]+1);
                }
            }
        }
        // 从右下到左上更新数组
        for(int i = m - 1;i >= 0;i--) {
            for (int j = n - 1;j >= 0;j--) {
                // 左边的
                if (i > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i + 1][j]+1);
                }
                // 右边的
                if (j > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i][j + 1]+1);
                }
            }
        }
        return dist;
    }
}

3、时间复杂度优化

仔细观察方法2的实现，可以发现有重复的操作。其实只需要两组不重复的更新即可。

要么是左上到右下的对角线，要么是左下到右上的对角线。

只要对于每一个1的位置，更新了上、下、左、右四个方向就行。

c++实现

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, INT_MAX / 2));
        // 如果 (i, j) 的元素为 0，那么距离为 0
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }
        // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) {
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        return dist;
    }
};
// 链接：https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/

Java实现

class Solution {
    public int[][] updateMatrix(int[][] matrix){
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dist = new int[m][n];
        // 初始化数组
        for(int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                if (matrix[i][j] == 1){
                    dist[i][j] = Integer.MAX_VALUE/2;
                }
            }
        }

        // 从左上遍历到右下，更新数组
        for(int i = 0;i < m;i++) {
            for (int j = 0;j < n;j++) {
                // 左边的
                if (i > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i - 1][j]+1);
                }
                // 右边的
                if (j > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i][j - 1]+1);
                }
            }
        }
        // // 从左下到右上更新数组
        // for(int i = m-1;i >= 0;i--) {
        //     for (int j = 0;j < n;j++) {
        //         // 左边的
        //         if (i > 0){
        //             dist[i][j] = Integer.min(dist[i][j],dist[i + 1][j]+1);
        //         }
        //         // 右边的
        //         if (j > 0){
        //             dist[i][j] = Integer.min(dist[i][j],dist[i][j - 1]+1);
        //         }
        //     }
        // }
        // // 从右上到左下更新数组
        // for(int i = 0;i < m;i++) {
        //     for (int j = n - 1;j >= 0;j--) {
        //         // 左边的
        //         if (i > 0){
        //             dist[i][j] = Integer.min(dist[i][j],dist[i - 1][j]+1);
        //         }
        //         // 右边的
        //         if (j > 0){
        //             dist[i][j] = Integer.min(dist[i][j],dist[i][j + 1]+1);
        //         }
        //     }
        // }
        // 从右下到左上更新数组
        for(int i = m - 1;i >= 0;i--) {
            for (int j = n - 1;j >= 0;j--) {
                // 左边的
                if (i > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i + 1][j]+1);
                }
                // 右边的
                if (j > 0){
                    dist[i][j] = Integer.min(dist[i][j],dist[i][j + 1]+1);
                }
            }
        }
        return dist;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com