Shortest Path in a Grid

Given a 2D grid consisting of open cells denoted by . and blocked cells denoted by #, a robot needs to find the shortest path from a starting cell to a target cell. The robot can move only in four directions: up, down, left, and right.

The grid is defined by two integers \(m\) and \(n\) representing the number of rows and columns respectively. Then, \(m\) lines follow each representing a row of the grid. Finally, a line containing four integers specifies the starting coordinates \((s_x, s_y)\) and the target coordinates \((e_x, e_y)\). Coordinates are 0-indexed.

If there is a valid path from the starting point to the target, output the shortest distance; otherwise, output -1.

inputFormat

The first line contains two integers \(m\) and \(n\) separated by a space, representing the grid dimensions.

The following \(m\) lines each contain a string of length \(n\) composed of characters . (open cell) and # (blocked cell).

The last line contains four integers \(s_x\), \(s_y\), \(e_x\), \(e_y\) separated by spaces representing the starting and ending coordinates respectively.

outputFormat

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

5 6
..#...
....#.
#..#..
....#.
..#...
0 0 4 4

8