Loading...
Loading...
Loading...
The college is planning a fire drill in its new exam block. The floor plan is a grid of r rows and c columns. A G is an exit gate, # is a wall and . is a room.
From any room or gate you can step to the cell directly above, below, left or right, if it is inside the plan and not a wall.
For every cell, print the fewest steps to the nearest gate. A gate is 0 steps from a gate. Print # for a wall, and −1 for a room from which no gate can be reached.
G, # or ..# for a wall, or −1 for a room with no reachable gate.G, # or ..Example 1
Input
3 4 .#G. ..#. G...
Output
2 # 0 1 1 2 # 2 0 1 2 3
The top-left room is 2 steps from the gate below it. The bottom-right room is 3 steps from either gate.
Example 2
Input
2 3 .#G ##.
Output
-1 # 0 # # 1
The top-left room is boxed in by walls, so it prints −1.
Try the problem first. Open one hint at a time.
Searching separately from every room repeats a lot of work. Search from the gates instead.
Put all gates in the queue at the start, each with distance 0. The search then spreads from every gate at the same speed.
The first time a room is reached, it is reached from its nearest gate, so its distance is final.
Start every distance at −1. Rooms that are never reached keep −1, which is exactly what to print.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor