Minimum Distance in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either empty (represented by a .) or an obstacle (represented by a #). Your task is to determine the minimum number of steps required to travel from a starting cell to a destination cell by moving up, down, left, or right.

If either the starting cell or destination cell is an obstacle, or if there is no path available, print -1.

Keep in mind that the allowed moves are only in the four cardinal directions, and the movement cost for each step is 1. The time complexity of an optimal solution is approximately \( O(n \times m) \).

inputFormat

The input is given from stdin and has the following format:

n m
row1
row2
... (n rows total)
sx sy dx dy

Here, n and m are integers denoting the dimensions of the grid. Each of the following n lines is a string of length m where '.' represents an empty cell and '#' represents an obstacle. The last line contains four integers: sx and sy are the 0-indexed row and column of the starting cell, and dx and dy are the 0-indexed row and column of the destination cell.

outputFormat

Output a single integer to stdout: the minimum number of steps required to travel from the starting cell to the destination cell. If the destination is unreachable, output -1.

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

9