← 返回 snowflake 的题目列表Nearest Bathroom Distance for Each Desk in a Grid (Multi-source BFS)
类型：online_judge
Problem
You are given a 2D grid grid of characters, where:
'B' denotes a Bathroom
'D' denotes a Desk
any other character (e.g. '.') denotes walkable empty space
Compute the shortest Manhattan distance from each Desk to its nearest Bathroom. You may move one step in 4 directions (up/down/left/right).
Return a 2D integer array dist with the same shape as grid:
if grid[i][j] == 'D', then dist[i][j] is the shortest distance to any Bathroom
otherwise dist[i][j] = -1
if a Desk cannot reach any Bathroom, its distance is -1
Input Format
Line 1: two integers m n
Next m lines: each is a string of length n describing the grid
Output Format
Print m lines, each with n integers (space-separated), representing the dist matrix.
Constraints
1 <= m, n <= 1000
The grid contains at least one 'D'
Number of 'B' >= 0
Examples
Example 1
Input:
3 4
..B.
.D..
...D
Output:
-1 -1 -1 -1
-1 2 -1 -1
-1 -1 -1 3
Example 2
Input:
2 3
DDD
BBB
Output:
1 1 1
-1 -1 -1
Example 3
Input:
2 2
DD
DD
Output:
-1 -1
-1 -1
-1 -1
Example 4
Input:
3 3
B..
...
..D
Output:
-1 -1 -1
-1 -1 -1
-1 -1 4
Example 5
Input:
1 5
DB..D
Output:
1 -1 -1 -1 4
Example
Input
3 4
..B.
.D..
...D
Output
-1 -1 -1 -1
-1 2 -1 -1
-1 -1 -1 3