Minimum Moves to Reach Target

You are given a grid of size \(N \times M\) where each cell is either walkable (denoted by '.') or contains an obstacle (denoted by '#'). From a given starting cell \((s_x, s_y)\) you need to reach the target cell \((e_x, e_y)\) in the minimum number of moves. You can move one step at a time in the four cardinal directions: up, down, left, or right.

If it is impossible to reach the target cell, output \(-1\).

The problem can be formally defined as follows: Given a grid with dimensions \(N \times M\), and two coordinate pairs for the start and end positions, determine the least number of moves needed to traverse from the start to the target or return \(-1\) if no such path exists.

inputFormat

The input is provided via standard input. The first line consists of two integers \(N\) and \(M\), the number of rows and columns in the grid. The following \(N\) lines each contain a string of length \(M\) which represents a row of the grid. The final line contains four integers: \(s_x\), \(s_y\), \(e_x\), and \(e_y\) indicating the starting cell and target cell respectively.

outputFormat

Output a single integer representing the minimum number of moves required to reach the target cell from the starting cell. If it is impossible to reach the target, output \(-1\).

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

8