Reppy's Minimum Energy

Reppy is trying to navigate through a grid with obstacles. The grid is represented as a matrix of characters where '.' denotes an open cell and '#' denotes an obstacle. Reppy can move in four directions (up, down, left, right) and each move costs 1 unit of energy. The goal is to determine the minimum amount of energy required for Reppy to travel from the starting position to the destination. If there is no possible path, output -1.

The energy cost can be expressed as:

\( E = \text{number of moves} \)

Coordinates are given in 1-indexed form.

inputFormat

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

n m
row1
row2
...
rown
r1 c1 r2 c2

Where:

• n and m are the number of rows and columns of the grid respectively.
• The next n lines each contain a string of length m representing the grid.
• The last line contains four integers r1, c1, r2, and c2, representing the starting and target positions (1-indexed).

outputFormat

Output a single integer to stdout representing the minimum amount of energy required to travel from the start to the destination. If no valid path exists, output -1.

## sample

5 5
.....
..#..
..#..
..#..
.....
1 1 5 5

8