Shortest Path in a Maze

You are given a maze represented as a grid of characters. The maze contains the following symbols:

• S: the starting cell
• E: the ending cell
• .: an open cell that you can traverse
• #: a wall that you cannot pass

Your task is to compute the shortest number of moves required to go from the starting cell $S$ to the ending cell $E$. You may move in the four cardinal directions: up, down, left, and right. If there is no valid path, output -1.

The problem can be modeled using the Breadth-First Search (BFS) algorithm on a grid. The distance or number of moves is defined as the count of steps taken from one cell directly adjacent (in one of the four directions) to the next.

inputFormat

The input is provided via standard input (stdin). The first line contains two integers $n$ and $m$, where $n$ is the number of rows and $m$ is the number of columns in the maze. Each of the following $n$ lines contains a string of length $m$ representing one row of the maze. The characters will be one of: '.', '#', 'S', or 'E'.

outputFormat

Output a single integer on standard output (stdout): the minimum number of moves required to reach the end cell $E$ from the start cell $S$. If no path exists, output -1.## sample

5 7
.......
.#.#.#.
.#S#E#.
.#.#.#.
.......

6