Skills101
← All coding problems

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 r lines: c characters each (., # or H, 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).

Loading editor…

Log in to run and submit your code — it's free.