Compute Nearest Destination Distances
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an `m x n` grid representing a city map.
Each cell contains one of the following characters:
- `D`: a destination
- `X`: an obstacle
- `.`: an open cell
For every cell in the grid, compute the length of the shortest path from that cell to the nearest destination.
Movement is allowed only in the four cardinal directions: up, down, left, and right.
Obstacle cells have a special rule:
- An `X` cell cannot be used as an intermediate cell in a path.
- However, you still must output a shortest distance value for every `X` cell as if the path starts from that obstacle cell and then moves to adjacent non-obstacle cells.
If a cell cannot reach any destination, output `-1` for that cell.
Return an `m x n` matrix of integers where each value is the shortest distance from the corresponding grid cell to its nearest destination.
Example:
Input:
```text
[
['.', '.', 'D'],
['X', '.', '.'],
['.', 'X', '.']
]
```
Output:
```text
[
[2, 1, 0],
[3, 2, 1],
[4, 3, 2]
]
```
Quick Answer: This question evaluates graph and grid traversal concepts, specifically multi-source shortest-path computation on a grid and handling special-cell constraints such as obstacles that cannot be used as intermediate steps.
You are given a rectangular city grid where each cell contains one of three characters: 'D' for a destination, 'X' for an obstacle, and '.' for an open cell.
For every cell, compute the length of the shortest path from that cell to the nearest destination.
Rules:
- You may move only up, down, left, or right.
- A path starting from a non-obstacle cell may move only through non-obstacle cells.
- An 'X' cell cannot be used as an intermediate cell in any path.
- However, you must still output a distance for every 'X' cell: treat the path as starting on that obstacle cell, then allow it to move to an adjacent non-'X' cell as its first step, and continue normally.
- The distance from a destination cell to itself is 0.
- If no destination is reachable, output -1 for that cell.
Return a matrix of the same size where each entry is the shortest distance to the nearest destination under these rules.
Constraints
- 0 <= m, n <= 500
- grid[i][j] is one of 'D', 'X', or '.'
- All rows have the same length
- An O(m * n) solution is expected
Examples
Input: ([['.', '.', 'D'], ['X', '.', '.'], ['.', 'X', '.']],)
Expected Output: [[2, 1, 0], [3, 2, 1], [-1, 3, 2]]
Explanation: Normal cells use BFS without passing through obstacles. Cell (2,0) cannot reach any destination because both possible directions are blocked by 'X'. Each 'X' cell gets 1 plus the best reachable neighboring non-'X' distance.