Shortest Path in a Grid

You are given a rectangular grid of size \(N \times M\) where each cell is either free (represented by '.') or blocked (represented by '#'). Your task is to determine the length of the shortest path from a given starting cell to a target cell. You can move in four directions: up, down, left, and right. If there is no valid path, output \(-1\).

Constraints:

• \(0 \leq \text{start}_x, \text{end}_x < N\)
• \(0 \leq \text{start}_y, \text{end}_y < M\)
• The grid contains only the characters '.' and '#'.

Note: The grid coordinates are 0-indexed. Use breadth-first search (BFS) to solve this problem efficiently.

inputFormat

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

N M
row1
row2
... 
rowN
start_x start_y
end_x end_y

Where:

• \(N\) and \(M\) are the number of rows and columns of the grid respectively.
• Each of the next \(N\) lines contains a string of length \(M\) representing a row of the grid.
• The next line contains two integers representing the starting coordinates.
• The last line contains two integers representing the ending coordinates.

outputFormat

For each test case, output a single integer on standard output (stdout) that represents the minimum number of moves needed to reach the target. If there is no valid path, output -1.## sample

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

8