Minimum Moves in a Grid

You are given a grid-based arena of size \( n \times m \) where each cell is either free (denoted by a period .) or blocked by an obstacle (denoted by a hash #). A robot starts at a given cell and needs to reach a goal cell. The robot can move one step at a time in one of the four cardinal directions (up, down, left, or right). The task is to compute the minimum number of moves required to go from the start to the goal.

If either the starting cell or the goal cell is blocked, or if there is no valid path from start to goal, output \(-1\). Otherwise, output the minimum number of moves. Recall that if the Manhattan distance between two points \((x_1,y_1)\) and \((x_2,y_2)\) is \(|x_1-x_2|+|y_1-y_2|\), this is the absolute lower bound on the moves required if no obstacles were present.

inputFormat

The input is given from standard input (stdin) in the following format:

n m
row_1
row_2
... (n rows total)
sx sy
gx gy

Where:

• n and m are integers representing the number of rows and columns of the grid.
• Each row_i is a string of length m consisting of characters . (free cell) and # (obstacle).
• sx sy are the 0-indexed row and column of the starting position.
• gx gy are the 0-indexed row and column of the goal position.

outputFormat

Output a single integer to standard output (stdout): the minimum number of moves required for the robot to reach the goal, or \(-1\) if it is impossible.

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

8