Shortest Path in a Minefield

You are given a grid of size r × c where each cell is either safe ('.') or contains a mine ('*'). Your task is to find the shortest path from a given starting cell to a destination cell. You are allowed to move up, down, left, or right. If there is no safe path from the start to the destination, output -1.

The problem can be formulated using the following LaTeX statement:

Find the minimum number of moves required to travel from \( (r_s, c_s) \) to \( (r_d, c_d) \) in a grid, using only adjacent moves (up, down, left, right), while avoiding cells containing mines. If the destination is unreachable, return -1.

inputFormat

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

r c
row1
row2
... 
row_r
r_start c_start
r_destination c_destination

Where:

• r and c are the numbers of rows and columns of the grid.
• Each of the next r lines contains a string of length c representing the grid row.
• r_start c_start represents the starting cell coordinates (0-indexed).
• r_destination c_destination represents the destination cell coordinates (0-indexed).

outputFormat

Output a single integer to stdout that gives the minimum number of moves required to reach the destination from the starting cell. If the destination is unreachable, output -1.

## sample

5 5
.....
.*...
.*.*.
.*...
.....
0 0
4 4

8

</p>