← 返回 doordash 的题目列表Distance to Nearest Destination on Grid (Including Obstacles)
类型：online_judge
Given an R x C 2D character grid board:
'd' marks a destination (there may be multiple),
'x' marks an obstacle cell,
any other character is a normal traversable cell.
Compute, for every cell, the shortest path distance (minimum number of steps) to the nearest destination 'd', and output an R x C integer matrix dist:
If a cell is 'd', then dist[r][c] = 0.
If a cell cannot reach any 'd', then dist[r][c] = -1.
Note: although 'x' represents an obstacle, you still must output a shortest distance value for 'x' cells as well (if reachable).
Movement rule: from a cell you may move one step to its 4-neighbors (up/down/left/right) within bounds.
Input
First line: two integers R C
Next R lines: each a string of length C describing the grid
Output
Print R lines, each with C space-separated integers representing the distance matrix.
Constraints
1 <= R, C <= 1000
There is at least one 'd' in the grid.
Sample Tests
(See the 5 test cases in the Chinese section.)
Example
Input
3 3
..d
...
...
Output
2 1 0
3 2 1
4 3 2