Treasure Hunt

Given an \(m \times n\) grid representing a treasure map, each cell of which is either grass (.) or a rock (#), your task is to determine the minimum number of moves required to reach the treasure.

You are provided with the starting cell \((x_1, y_1)\) and the treasure cell \((x_2, y_2)\). You may move one step at a time in one of the four cardinal directions: up, down, left, or right.

If the treasure is unreachable, output \(-1\). Note that the grid cells are 0-indexed and each move increases the move count by 1.

inputFormat

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

m n
grid_row_1
grid_row_2
... 
grid_row_m
x1 y1 x2 y2

Here, \(m\) and \(n\) represent the number of rows and columns of the grid respectively. Each of the next \(m\) lines contains a string of exactly \(n\) characters (either . for grass or # for rock). The final line contains four integers: the starting position \((x_1, y_1)\) and the treasure position \((x_2, y_2)\).

outputFormat

Output a single integer to standard output (stdout): the minimum number of moves needed to reach the treasure, or \(-1\) if it is unreachable.

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

8