Maze Navigation

You are given a maze represented by an n × m grid. Each cell in the grid is one of the following:

• s for the starting point
• e for the exit point
• . for an open space
• # for an obstacle

Your task is to find the shortest path from the starting point to the exit. The movement is allowed only in the four cardinal directions (up, down, left, right).

If there is no valid path from s to e, output -1. Otherwise, output the number of steps in the shortest path.

The problem can be mathematically modeled using the following formula:

\( d = \min \{ \text{steps}(s \to e) \}\), where if no path exists then \(d = -1\).

inputFormat

The first line contains two integers n and m \( (1 \leq n, m \leq 1000)\), representing the number of rows and columns in the grid respectively. The following n lines each contain a string of length m, which represents a row of the maze.

outputFormat

Output a single integer: the length of the shortest path from the starting point to the exit. If there is no such path, output -1.

5 5
s#...
.#.#.
.#...
.###.
...e.

7