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:
[
['.', '.', 'D'],
['X', '.', '.'],
['.', 'X', '.']
]
Output:
[
[2, 1, 0],
[3, 2, 1],
[4, 3, 2]
]