Shortest Path in a Grid

You are given a grid consisting of R rows and C columns. Each cell in the grid is represented by a character: a dot ('.') indicates an open cell, and a hash ('#') indicates an obstacle. You need to compute the minimum number of steps required to go from a given starting cell (Sr, Sc) to a destination cell (Dr, Dc). You are allowed to move one cell at a time in four directions: up, down, left, and right. If there is no valid path, output -1.

More formally, let (G) be a grid with (R) rows and (C) columns. A cell (G_{i,j}) is traversable if (G_{i,j} = '.'). Find the minimum number of moves to reach (G_{Dr, Dc}) starting from (G_{Sr, Sc}) using moves of the form ((i,j) \rightarrow (i+1,j)), ((i,j) \rightarrow (i-1,j)), ((i,j) \rightarrow (i,j+1)), or ((i,j) \rightarrow (i,j-1)). If no such path exists, output (-1).

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers (R) and (C) — the number of rows and columns in the grid.
2. The second line contains four integers (Sr), (Sc), (Dr), and (Dc) representing the starting cell coordinates and destination cell coordinates (0-indexed).
3. This is followed by (R) lines, each containing a string of length (C) composed only of the characters '.' and '#'.

outputFormat

Output a single integer: the minimum number of steps required to reach the destination cell from the starting cell. If there is no valid path, output -1.## sample

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

8