Leetcode 542. 01 Matrix

[medium]

https://leetcode.com/problems/01-matrix/

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

[Java]

1. It’s a classic BFS kind of question. Scan throw all the 0s, and put 0’s location in the queue. Change the rest of 1s into Integer.MAX_VALUE
2. poll the int[i, j] from the queue, and check four different direction spots. If current number is larger than new count, update the shortest way to the spots.