Minimum Moves in a Grid

You are given a grid with n rows and m columns. Each cell in the grid is either an open cell denoted by . or an obstacle denoted by #. Your task is to determine the minimum number of moves required to travel from a specified start cell to a target cell using only the four cardinal directions (up, down, left, right). Moves can only be made into open cells. If the target cell is unreachable, output -1.

Note: The start or target cell might be an obstacle. In such cases, the answer is -1.

The movement is allowed from a cell (r, c) to its adjacent cells (r-1, c), (r+1, c), (r, c-1), and (r, c+1) provided that the new position is within the grid bounds and is not blocked by an obstacle.

The solution can be efficiently determined using a Breadth-First Search (BFS) algorithm.

inputFormat

The input is given from stdin and follows the format below:

 n m
 grid_row_1
 grid_row_2
 ...
 grid_row_n
 sr sc
 tr tc

Where:

• n and m are the number of rows and columns respectively.
• Each of the next n lines represents a row of the grid containing . and #.
• sr sc are the 0-indexed starting row and column numbers.
• tr tc are the 0-indexed target row and column numbers.

outputFormat

Output the minimum number of moves (an integer) required to reach the target from the start cell. If it is impossible to reach the target, output -1.

The output should be printed to stdout.

## sample

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

8