Shortest Path in a Grid

You are given a grid of size n rows and m columns. Each cell of the grid is represented by one of the following characters:

• 'S': the starting point.
• 'E': the destination point.
• '.': an empty cell you can walk on.
• '#': a wall that you cannot pass.

You can move from a cell to one of its four adjacent cells (up, down, left, or right) if the destination cell is not a wall. The task is to compute the minimum number of steps required to travel from S to E. If there is no valid path between S and E, output -1.

The distance is defined as the number of moves. In mathematical terms, if you denote the number of moves by \( d \), the solution finds the minimum \( d \) such that there exists a sequence of moves from S to E following the allowed directions.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers \( n \) and \( m \) (\( 1 \leq n, m \leq 1000 \)), representing the number of rows and columns of the grid.
2. The next \( n \) lines each contain a string of length \( m \) consisting only of characters from the set {'.', '#', 'S', 'E'}.

You can assume that both 'S' and 'E' appear exactly once in the grid.

outputFormat

Output a single integer to standard output (stdout): the minimum number of moves required to reach the destination 'E' from the starting point 'S'. If there is no valid path, output -1.

1 2
SE

1