Distance From Every Cell to the Nearest Empty Slot

Implement nearestZero

You are given a grid of 0s and 1s containing at least one 0. For every cell, find the number of steps needed to reach the nearest cell that holds 0, moving up, down, left or right one cell at a time. Return the grid of these distances.

Measuring from each cell to every zero works but is slow. A breadth-first search that starts from all zeros simultaneously computes every distance in a single sweep.

Example 1:

Input: grid = [[1,1,0],[1,1,1],[0,1,1]]

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

Example 2:

Input: grid = [[0,0],[0,0]]

Output: [[0,0],[0,0]]

Example 3:

Input: grid = [[1,1,1,0]]

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

+ 12 hidden test cases run on Submit.

Constraints:

  • ●1 ≤ rows, cols ≤ 12; grid[r][c] is 0 (an empty slot) or 1 (an occupied slot); the grid contains at least one 0
  • ●You can move between cells that share a side (up, down, left, right); every step costs 1 and every cell can be entered
  • ●For every cell, compute the number of steps to the nearest cell holding 0 (0 for the empty slots themselves)
  • ●Return the grid of distances (same size as the input)

grid =

[[1,1,0], [1,1,1], [0,1,1]]