Graphs Fewest steps with BFS
443. 01 Matrix
You are given a grid mat in which every cell holds 0 or 1. For every cell, find the distance to the
nearest cell that holds 0. Return these distances as a grid of the same size.
The distance between two cells is the number of steps it takes to walk from one to the other. A step moves to the cell directly above, below, left or right. Diagonal steps are not allowed. A cell that holds 0 has distance 0.
Example 1
Input: mat = [[0, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, 1]]
[[0,1,2,1],[1,2,1,0],[2,3,2,1]]Explanation: The cell at row 2, column 1 is three steps from either 0, the most of any cell. The cell at row 0, column 2 is two steps from both 0s.
Example 2
Input: mat = [[1, 1, 0, 1, 1, 1]]
[[2,1,0,1,2,3]]Explanation: The only 0 is in column 2. Each cell's distance is how far its column is from column 2.
Example 3
Input: mat = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
[[2,1,2],[1,0,1],[2,1,2]]Explanation: The corners touch the 0 only at a corner, so each one needs two steps, such as one right and one down.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == mat.length,n == mat[i].length1 ≤ m, n ≤ 1051 ≤ m · n ≤ 105mat[i][j]is 0 or 1.matholds at least one 0.
Clarifying questions
What you would ask an interviewer before writing any code.