Shortest Path on a Grid
Given a labyrinth represented as a grid of
r rows and c columns, you are asked to find the length of the shortest path from the starting cell to the end.The labyrinth is represented with:
- The floor is a dot (
.).
- The walls are hashtags (
#).
- The starting point is the capital letter
S.
- The end cell is the capital letter
E.
You can move between two adjacent cells (left, right, up, or down) if they’re not walls.
You are asked to find the length of the shortest path between the starting cell and the end cell.
Input
The first line of the input contains two integers
r and c (1 ≤ r, c ≤ 1000).The next
r rows contain c columns of characters representing the grid. Each cell is either a floor (.), a wall (#), a starting point (S), or an endpoint (E). It’s guaranteed that there is only a single S and a single E in the whole grid.Output
The program should print the length of the shortest path from
S to E. If there is no path from S to E, the program should print Impossible.Examples
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Tip
It’s not always necessary to construct a graph to run a BFS algorithm. Sometimes, you can have implicit graphs like grids and still be able to run a BFS algorithm on them.
Hint
You can treat the grid as your graph and have a two-dimensional array of distances
d[][] representing the shortest distance from the starting cell up to the current one.Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB