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.
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.
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.