LeetCode 542. 01 Matrixleetcode,bfs,算法村里的原振侠的博客-

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.

Example 1:

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

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

Solution:

思路使用bfs不是很难，主要是有点抽象。

1. 先把所有0点放入queue，然后把所有1点设置为无穷大
2. 然后遍历所有queue中的0点，如果0点上下左右四个位置有无穷大的位置则设置为1。（表明它和0的距离是1） 然后把这个1点放入队列queue
3. 遍历完0点后，所有0点周围都是1点，然后继续遍历1点，如果存在无穷大（Integer.MAX_VALUE），则把这个点设置为2（表明它和1点的距离为1，和0点的距离为2）
4. 以此类推，直到所有点遍历完。DFS是一次走到底，所以要用stack保留之前信息，BFS每次只走一步，新添加的待遍历点放入queue，等之后再遍历。

public int[][] updateMatrix(int[][] matrix) {          Queue<Integer[]> bfs = new LinkedList<>(); int dist = 0; int m = matrix.length, n = matrix[0].length; for(int i = 0; i < matrix.length; i++){ for(int j = 0; j < matrix[i].length; j++){ if(matrix[i][j] == 0) bfs.offer(new Integer[]{i, j}); // keep track of all 0's else matrix[i][j] = Integer.MAX_VALUE; // else initialize distance to infinity } } int[][] directions = {{1,0}, {-1, 0}, {0, 1}, {0, -1}}; while(!bfs.isEmpty()){             Integer[] current = bfs.poll(); for(int[] d : directions){ int i = current[0] + d[0]; int j = current[1] + d[1]; // if new cell is out of bounds or is already closer to another 0, stop further bfs in this cell if(i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] <= matrix[current[0]][current[1]] + 1) continue;                  bfs.offer(new Integer[] {i, j}); // put in queue for further bfs operations                 matrix[i][j] = matrix[current[0]][current[1]] + 1; // update new smaller distance } } return matrix; }