Compute distance to nearest taxi in grid
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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?
Quick Answer: This question evaluates understanding of graph traversal and shortest-path reasoning on grids, algorithmic problem-solving for computing distances from many targets, and the ability to manage time and space complexity on large inputs.