542. 01 Matrix

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 00 1 00 0 0

Output:

0 0 00 1 00 0 0

Example 2: Input:

0 0 00 1 01 1 1

Output:

0 0 00 1 01 2 1

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

class Solution { public int[][] updateMatrix(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; Queue q = new LinkedList<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) q.add(new int[]{i, j}); //把0元素加入队列中，以备波及影响周围元素 else matrix[i][j] = Integer.MAX_VALUE;//设为最大值，方便求0元素影响值 } } //溅起的涟漪，代表传播的四个方向 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!q.isEmpty()) { int[] cell = q.poll(); for (int[] dirc : dirs) { //需要比较的下一位置元素 int r = cell[0] + dirc[0]; int c = cell[1] + dirc[1]; //如果下一位置的元素值，小于等于（当前位置元素值+1），直接跳过 if (r < 0 || r >= m || c < 0 || c >= n || matrix[r][c] <= (matrix[cell[0]][cell[1]] + 1)) continue; else { matrix[r][c] = matrix[cell[0]][cell[1]] + 1; q.offer(new int[]{r, c}); } } } return matrix; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。