Loading...
Loading...
Loading...
The college fest has a maze game. The maze is a grid of r rows and c columns. A . is an open cell, # is a wall, S is where you start and E is the exit. S and E are open cells too.
In one move you step to the cell directly above, below, left or right, if it is inside the maze and not a wall.
Print the fewest moves needed to go from S to E. If the exit cannot be reached, print −1.
., #, S or E.S and exactly one E.Example 1
Input
4 5 S.#.. .##.# ...#E #....
Output
8
Go down to the third row, right, down to the bottom row, right to the last column and up to E.
Example 2
Input
3 3 S#. ##. ..E
Output
-1
Walls close S in, so the exit cannot be reached.
Try the problem first. Open one hint at a time.
Explore the maze in rings: first every cell 1 move away, then every cell 2 moves away, and so on.
A queue does exactly this. The first time a cell is added, its distance is one more than the cell it was reached from.
Keep a distance array filled with −1. A cell with −1 has not been reached yet.
Mark a cell when you add it to the queue. When the queue is empty, the distance of E is the answer, still −1 if it was never reached.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor