Compute distance to nearest taxi in grid

You are given an R x C grid representing a city map.

• grid[r][c] = 1 means there is a taxi located at cell (r, c) .
• grid[r][c] = 0 means the cell is empty.
• You can move from a cell to its 4-directional neighbors (up/down/left/right). Each move costs 1.

Return an R x C matrix dist where dist[r][c] is the length of the shortest path from cell (r, c) to any taxi.

If a cell cannot reach any taxi, set its distance to -1.

Input

• grid : a 2D array of 0/1 integers

Output

• dist : a 2D array of integers

Constraints (typical interview bounds)

• 1 <= R, C <= 2000 (or any size where an O(R*C) solution is expected)
• There may be 0 taxis or many taxis.

Follow-ups

1. Is DFS an appropriate alternative here if we want shortest distances? Why or why not?
2. What changes if movement is allowed in 8 directions instead of 4?