Distance to the Nearest Hospital
mediumGraphs II+20 XPTime limit 2s
A city map is a grid. Each cell is a road ., a building # (you cannot walk through it) or a hospital H. From every cell you can walk up, down, left or right to a neighbouring non-building cell in one minute. For every cell, find how many minutes it takes to reach the nearest hospital.
Input:
- line 1:
r c - next
rlines:ccharacters each (.,#orH, no spaces)
Output: r lines of c numbers: the walking time from that cell to the nearest hospital (0 on a hospital). Print -1 for buildings and for cells that cannot reach any hospital.
Constraints: 1 ≤ r, c ≤ 300. There may be no hospital at all.
Think about it: one BFS per hospital is far too slow when there are thousands of hospitals. Instead put all hospitals in the queue at distance 0 and run a single multi-source BFS — each cell is reached first from its nearest hospital. O(r · c).
Sample input 1
3 4 .H.. .##. ...H
Sample output 1
1 0 1 2 2 -1 -1 1 3 2 1 0
Sample input 2
2 3 .#. #H.
Sample output 2
-1 -1 2 -1 0 1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).