Minimum Cost Transport

You are given an m × n grid where each cell is either free (represented by a dot '.') or blocked (represented by a hash '#'). An amenity is located at the start cell, and you need to transport it to the destination cell. Moves are allowed in four directions (up, down, left, right) with a cost of 1 per move. The task is to determine the minimum cost (i.e. the minimum number of moves) required to travel from the start to the destination while avoiding obstacles. If the destination is unreachable, output -1.

The problem can be formulated as finding the shortest path in a grid. In mathematical terms, if you let \(d(x, y)\) denote the minimum number of moves to reach cell \((x,y)\), the recurrence is given by:

\[ d(x, y) = \min_{(x',y') \in \mathcal{N}(x,y)} \{ d(x',y') + 1 \} \]

with \(\mathcal{N}(x,y)\) representing the neighboring cells that are valid (inside the grid and not blocked).

inputFormat

The input is given via standard input (stdin) and has the following format:

<m> <n>
<row 1 of grid>
<row 2 of grid>
...
<row m of grid>
<start_x> <start_y>
<end_x> <end_y>

where:

• m and n are the dimensions of the grid.
• Each of the next m lines represents a row of the grid and consists of exactly n characters (either '.' or '#').
• start_x and start_y denote the starting cell coordinates.
• end_x and end_y denote the destination cell coordinates.

outputFormat

Output a single integer to the standard output (stdout) representing the minimum number of moves needed to go from the start to the destination. If the destination cannot be reached, output -1.

## sample

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

8