Leetcode 542. 01 矩阵

题目

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example1：

image.png

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example2:

image.png

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

解题思路

这道题的要求是求出每个cell到0的距离，可以用BFS和DP两种方法来做。

方法	时间复杂度	空间复杂度
BFS	O(mn)	O(mn)
DP	O(4mn)	O(1)

1. BFS

BFS的思路是，找到起点节点，然后以起点为圆心，一层一层扩散的方式，遍历所有的节点。

BFS的实现模板，就是使用队列来实现。

模板代码如下：

   private void bfs(Node root){
        Queue<Node> queue = new LinkedList<>();
        // 先把起点加入队列
        queue.offer(root);
        while(!queue.isEmpty()){
            int node = queue.poll();
            // 把所有的下一层级的孩子，加入队列
            for(Node child : node.children){
                queue.offer(child);
            }
        }
    }

这道题是典型的BFS的思路。

• 题目要求节点到0的距离，所以我们知道，所有0节点的值都是0。那我们可以把这个0节点作为起点，先加入队列。
• 记录一个全局的变量level，表示节点离0节点的层数。
• 然后找到0节点周围的所有1节点，遍历他们，并设置层数level，然后将这些节点加入队列，继续遍历。
• 直到所有的节点都遍历完。

注意：为了防止重复遍历死循环，已经遍历过的节点，不要重复遍历。

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[][] res = new int[n][m];
        // 保存已经遍历过的节点
        boolean[][] visited = new boolean[n][m];
        // BFS模板代码
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < m; j++){
                // 先把所有的0节点加入queue，作为起点
                if(mat[i][j] == 0){
                    visited[i][j] = true;
                    queue.add(new int[]{i, j});   
                }
            }
        }
        // 遍历四个方向的节点
        int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int i = cur[0], j = cur[1];
            for(int k = 0; k < directions.length; k++){
                int r = i + directions[k][0];
                int c = j + directions[k][1];
                // 判断坐标值是否有效 & 是否访问过
                if(r >= 0 && r < n && c >= 0 && c < m && !visited[r][c]){
                    res[r][c] = res[i][j] + 1;
                    visited[r][c] = true;
                    queue.add(new int[]{r, c});
                }
            }
        }
        return res;
    }
}

2. DP

这道题很直接得能想到用DP去做。递推公式如下：

如果mat[i][j] == 0 则 dp[i][j] = 0
如果mat[i][j] != 0 则 dp[i][j] = 1 + min(dp[i-1][j], dp[i+1][j], [dp[i][j-1], dp[i][j+1])

一般DP都是从一个方向开始，做DP。而这道题需要从四个方向分别做DP，最后取DP结果的最小值。

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] dp = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(mat[i][j] == 0){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = Math.max(n, m) + 1;
                }
            }
        }
        // 从左上方来的
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(i > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);
                }
                if(j > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + 1);
                }
            }
        }
        // 从左下方来
        for(int i = n - 1; i >= 0; i--){
            for(int j = 0; j < m; j++){
                if(i < n-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i+1][j] + 1);
                }
                if(j > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + 1);
                }
            }
        }
        // 从右上方来
        for(int i = 0; i < n; i++){
            for(int j = m-1; j >= 0; j--){
                if(i > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + 1);
                }
                if(j < m-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j+1] + 1);
                }
            }
        }
        // 从右下方来
        for(int i = n-1; i >= 0; i--){
            for(int j = m-1; j >= 0; j--){
                if(i < n-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i+1][j] + 1);
                }
                if(j < m-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j+1] + 1);
                }
            }
        }
        return dp;
    }
}

总结

这道题我们用了BFS和DP两种方法来做，两种方法都比较直观。有几点需要注意：

• BFS采用以0为起点的方法，多路同时进行。为了避免发生死循环，需要记录已经访问过的节点。
• DP需要从四个方向做DP，然后取最小值作为结果，如果只从一个方向DP，结果不是最优解。