LeetCode 01 Matrix

· 633 words · 2 minute read
2017年7月
LeetCode

542. 01 Matrix

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

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

Tips: cell为0则距离该cell最近的0的距离为0，即为该cell自身

方法

新题型！！！

一看到这道题一开始就考虑使用DFS,可是一细想求1到0的最短距离，如果用dfs,对应4个方向那就要使用Math.min(上，下，左，右)。估计会超时。

此时就应该换个思路，假设一下如果计算0到1的距离呢，对！使用BFS。刷了这么多到题，都已经想当然DFS了，这题来个BFS很有必要。

首先遍历一次矩阵，将值为0的点都存入queue，将值为1的点改为INT_MAX。之前像什么遍历迷宫啊，起点只有一个，而这道题所有为0的点都是起点。然后开始BFS遍历，从queue中取出一个数字，遍历其周围四个点，如果越界或者周围点的值小于等于当前值，则直接跳过。因为周围点的距离更小的话，就没有更新的必要，否则将周围点的值更新为当前值加1，然后把周围点的坐标加入queue，得解

注意：这道题遍历4个方向的方法，一般可以用一个二维数组来存储4个方向

public class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return matrix;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0)
                    queue.add(new int[]{i,j});
                else
                    matrix[i][j] = Integer.MAX_VALUE;
            }
        }
        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        while(queue.size() != 0){
            int[] matr = queue.poll();
            for(int[] d : directions){
                int x1 = matr[0]+d[0];
                int y1 = matr[1]+d[1];
                if(x1 < 0 || x1 >=m || y1 < 0 || y1 >= n || matrix[x1][y1] < matrix[matr[0]][matr[1]] + 1){
                    continue;
                }
                matrix[x1][y1] = matrix[matr[0]][matr[1]] + 1;
                queue.add(new int[]{x1,y1});
            }
        }
        return matrix;
    }
}
Share