【刷题】Leetcode 542. 01 Matrix

最近在刷搜索，DFS，BFS，backtracking的题。

如果你是初学者，建议多看一些模版，然后一定动手写。我在上学的时候，对这些代码就只是看过，过了脑子，等自己写的时候，会发现很多问题。

最近更新的代码DFS的一个套路，BFS的一个套路，然后等遇到具体问题具体分析。

这道题莫名的看了半天solution，又取层数，又判断距离的，没想明白。最后直接写BFS也就过了。

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.

Example 1:

Input:
[[0,0,0],
[0,1,0],
[0,0,0]]

Output:
[[0,0,0],
[0,1,0],
[0,0,0]]
Example 2:

Input:
[[0,0,0],
[0,1,0],
[1,1,1]]

Output:
[[0,0,0],
[0,1,0],
[1,2,1]]

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        Queue<int[]> list = new LinkedList<int[]>();
        int[][] direc = new int[][]{
            {0,1}, {0,-1}, {1, 0}, {-1, 0}
        };
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    list.offer(new int[]{i, j});
                }else if(matrix[i][j] == 1)
                    matrix[i][j] = -1;
            }
        }
        
        while(!list.isEmpty()){
            int[] cell = list.poll();
            for(int i = 0; i < direc.length; i++){
                int nextRow = cell[0] + direc[i][0];
                int nextCol = cell[1] + direc[i][1];
                if(nextRow >= 0 && nextRow < matrix.length
                  && nextCol >= 0 && nextCol < matrix[0].length){
                    if(matrix[nextRow][nextCol] == -1){
                        matrix[nextRow][nextCol] = matrix[cell[0]][cell[1]] + 1;
                        list.offer(new int[]{nextRow, nextCol});
                    }
                }
            }
        }
        return matrix;
    }
}

总结

• 判断if(matrix[nextRow][nextCol] == -1)，没访问过的才访问，更新过的就不会再遍历到了。