Shortest Route in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either open (denoted by '.') or blocked (denoted by '#'). Your task is to compute the length of the shortest path from a given starting position to a goal position.

Movement is allowed in the four cardinal directions: up, down, left, and right. The grid coordinates are provided in a 1-indexed format. If a path does not exist, output -1.

The problem can be formulated as follows:

Find the minimum number of steps required to move from the start cell to the goal cell, where each move from one cell to an adjacent open cell counts as a single step. Mathematically, if the path is represented as a sequence of steps, then the distance is given by:

$$d = \min_{\text{path}} \sum_{(x,y) \in \text{path}} 1 $$

If no such path exists, return -1.

inputFormat

The input is provided via standard input (stdin) in the following format:

• The first line contains two integers n and m representing the number of rows and columns.
• The next n lines each contain a string of length m representing the grid. Each character is either '.' (an open cell) or '#' (a blocked cell).
• The following line contains two integers representing the starting cell's coordinates (1-indexed).
• The last line contains two integers representing the goal cell's coordinates (1-indexed).

outputFormat

Output a single integer via standard output (stdout): the length of the shortest path from the start to the goal. If the goal is unreachable, output -1.

## sample

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

8