01 Matrix

You get a grid of 0s and 1s. It is an array of rows, and each row is an array of integers.

Return a grid of the same size. Each cell in it holds the number of steps to the closest 0.

A step moves one cell up, down, left or right. You can't move diagonally. A cell that holds 0 is 0 steps away.

Example 1:

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

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

Explanation: Each 1 that touches a 0 gets 1.
The 1 at row 2, column 2 (counting from 0) touches no 0.
Its closest 0 is 2 steps away: up, then right.

Example 2:

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

Output:
[[2,1,0,1,2,3]]

Explanation: There is one row with one 0.
The count grows by 1 with each cell away from it.

Example 3:

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

Output:
[[4,3,2],
 [3,2,1],
 [2,1,0]]

Explanation: The only 0 is in the bottom-right corner.
The top-left cell is 2 rows up and 2 columns left of it.
So it is 2 + 2 = 4 steps away.

Constraints:

• 1 to 10,000 cells in all.
• The grid can be 100 rows of 100 or one row of 10,000.
• All rows have the same length.
• Every cell is 0 or 1.
• At least one cell is 0.