Shortest Path in a Grid

This problem requires you to determine the minimum number of steps required to travel from a starting cell to a destination cell in a grid. The grid is represented as an R×C matrix, where each cell is either passable (denoted by .) or blocked (denoted by #). You can only move in four directions: up, down, left, or right.

If there exists a valid path from the starting cell to the destination cell, output the length of the shortest path. Otherwise, output \(-1\).

Movement constraints:

• You may move from cell \((i,j)\) to cell \((i+1,j)\), \((i-1,j)\), \((i,j+1)\), or \((i,j-1)\) if the target cell lies within the grid and is passable.

inputFormat

The first line contains two space-separated integers R and C representing the number of rows and columns of the grid.

The next R lines each contain a string of length C composed of the characters . and #, representing the grid.

The following line contains two space-separated integers Sr and Sc, the row and column indices of the starting cell (0-indexed).

The last line contains two space-separated integers Dr and Dc, the row and column indices of the destination cell (0-indexed).

outputFormat

Output a single integer representing the length of the shortest path from the starting cell to the destination cell. If no valid path exists, output -1.

## sample

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

4