Shortest Path in a Grid

Given a grid of size \(M \times N\) where each cell is marked with one of the following characters:

• S - starting point
• E - ending point
• . - an open cell
• * - a blocked cell

Your task is to determine the length of the shortest path from the start ('S') to the end ('E'). Movement is allowed in four directions: up, down, left, and right. If there is no valid path between 'S' and 'E', output -1.

Note:

• The grid dimensions satisfy \(1 \le M, N \le 100\).
• The input is provided via standard input and the result should be printed to standard output.

inputFormat

The first line of input contains two space-separated integers, \(M\) and \(N\), representing the number of rows and columns, respectively. This is followed by \(M\) lines, each containing a string of length \(N\) composed of the characters: 'S', 'E', '.', and '*'.

outputFormat

Output a single integer representing the length of the shortest path from 'S' to 'E'. If there is no valid path, output -1.

5 5
S....
.*.*.
.*.*.
....*
...E*

7