542. 01 Matrix
https://leetcode.com/problems/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:
- 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.
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int[][] updateMatrix(int[][] matrix) { | |
| Queue<int[]> q = new LinkedList<int[]>(); | |
| // BFS starting from all 0's | |
| for (int r = 0; r < matrix.length; r++) { | |
| for (int c = 0; c < matrix[0].length; c++) { | |
| if (matrix[r][c] == 0) { | |
| q.offer(new int[]{r, c}); | |
| } else { | |
| matrix[r][c] = Integer.MAX_VALUE; | |
| } | |
| } | |
| } | |
| int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; | |
| while (!q.isEmpty()) { | |
| int[] current = q.poll(); | |
| for (int[] d: dirs) { | |
| int nr = current[0] + d[0]; | |
| int nc = current[1] + d[1]; | |
| // Is neighbor unvisited 1 | |
| if (isValid(matrix, nr, nc)) { | |
| // mark visited, save ans | |
| matrix[nr][nc] = 1 + matrix[current[0]][current[1]]; | |
| q.offer(new int[]{nr, nc}); | |
| } | |
| } | |
| } | |
| return matrix; | |
| } | |
| private boolean isValid(int[][] matrix, int nr, int nc) { | |
| return nr >= 0 && nr < matrix.length && nc >= 0 && nc < matrix[0].length && matrix[nr][nc] == Integer.MAX_VALUE; | |
| } | |
| } |
