[Java] 542. 01 Matrix

Description

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

记录矩阵中每个元素到其最近0的距离

Solution

法1：BFS

（看到这个题突然想到扫雷。。。

1. 以0为中心向外扩散传播，第一层将0加入队列，第二层将0周围元素赋值为1加入队列，以此类推；
2. 因为计算距离最小为0，位置为0的地方值一定还为0，所以首先可以考虑将1的位置赋值为整数最大值；
3. matrix[r][c] <= matrix[cell[0]][cell[1]] + 1 说明此点已被遍历过；

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        // BFS  先将所有0的位置加入队列，将所有1的位置设为INF  
        int m = matrix.length;
        int n = matrix[0].length;
        
        Queue<int[]> 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 int[] {i, j});
                }
                else{
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};  //四个方向
        
        while(!queue.isEmpty()){
            int[] cell = queue.poll();   //存进队列中的是坐标点
            for(int[] d : dirs){
                int r = cell[0]+d[0];
                int c = cell[1]+d[1];
                if(r >= m || r < 0 || c >= n || c < 0 || matrix[r][c] <= matrix[cell[0]][cell[1]] + 1)
                    continue;
                queue.add(new int[] {r,c});
                matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
            }   
        }
        return matrix;
    }
}

另：BFS常用visited数组标记原来在队列中，现在已出队列的点，将此标记法也贴一下

    public int[][] updateMatrix(int[][] matrix) {
        // BFS  先将所有0的位置加入队列  visited标记是否访问过
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        
        Queue<int[]> 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 int[] {i, j});
                    visited[i][j] = true;  //表示访问过了
                }
            }
        }
         
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};  //四个方向
        
        while(!queue.isEmpty()){
            int[] cell = queue.poll();   //存进队列中的是坐标点
            for(int[] d : dirs){
                int r = cell[0]+d[0];
                int c = cell[1]+d[1];
                if(r >= m || r < 0 || c >= n || c < 0 ||visited[r][c] == true)  //遇到不合法的点或访问过的点，跳过
                    continue;
                queue.add(new int[] {r,c});  //即将以其为起点进行搜索
                matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
                visited[r][c] = true;
            }   
        }
        return matrix;
    }
}

法2：动态规划