Shortest Path in Maze

Given a 2D grid maze with open cells represented by . and walls represented by #, your task is to find the shortest path between the given starting cell and target cell. Movement is allowed in four directions – up, down, left, and right – and you may only travel on open cells.

If there is no valid path, output -1.

The problem can be formulated as follows: Given a maze \(M\) of size \(n \times m\), a starting cell \((s_x, s_y)\) and an ending cell \((e_x, e_y)\), determine the minimum number of moves required to go from \((s_x, s_y)\) to \((e_x, e_y)\). The answer is \(0\) if the start and end cells are the same and \(-1\) if the target cell is unreachable.

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 \le n, m \le 1000\)) indicating the number of rows and columns of the maze.
2. The next \(n\) lines each contain a string of length \(m\) composed of the characters . and #, representing the maze.
3. The following line contains two space-separated integers \(s_x\) and \(s_y\) (0-indexed) representing the starting cell.
4. The last line contains two space-separated integers \(e_x\) and \(e_y\) (0-indexed) representing the target cell.

outputFormat

Output a single integer: the minimum number of steps required to move from the starting cell to the target cell. If no valid path exists, output -1.

3 3
...
##.
...
0 0
2 2

4