Shortest Path in a Grid

You are given a grid of size \( N \times M \) consisting of empty cells represented by '.' and obstacles represented by '*'. Your task is to find the shortest path from a starting cell to a target cell. Movement is only allowed up, down, left, or right, and diagonal movements are not permitted.

The input positions (for both the start and target) are given in 1-indexed format. If either the starting cell or the target cell is an obstacle, or if there is no valid path between them, output \(-1\).

The problem can be solved using a breadth-first search (BFS) algorithm.

inputFormat

The first line contains two integers ( N ) and ( M ) denoting the number of rows and columns respectively. The following ( N ) lines each contain a string of length ( M ), describing the grid. The next line contains two integers representing the starting cell (row and column). The last line contains two integers representing the target cell (row and column). All positions are 1-indexed.

outputFormat

Output a single integer representing the length of the shortest path from the start cell to the target cell. If no such path exists, output (-1).## sample

5 7
.......
.*.*.*.
.......
.*.*.*.
.......
1 1
5 7

10