Robot Shortest Path in a Grid

You are given a grid of dimension \(n \times m\) that represents a lab. Each cell in the grid is represented by either '.' (a free cell) or '#' (an obstacle). A robot is positioned at a starting cell \((S_x, S_y)\) and must move to a target cell \((T_x, T_y)\) using the four cardinal directions (up, down, left, right). Your task is to compute the length of the shortest path (measured in steps) the robot takes to reach the target, or output -1 if it is impossible.

The movement is subject to the following details:

• The robot cannot move diagonally.
• The robot cannot enter a cell that contains an obstacle.
• If either the starting cell or the target cell is an obstacle, the output should be -1.
• If the starting cell is the same as the target cell, the shortest path length is 0.

The problem can be solved using a Breadth-First Search (BFS) to explore the grid. The distance is essentially the number of steps taken from the start to the target.

inputFormat

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

 n m
 grid[0]
 grid[1]
 ...
 grid[n-1]
 S_x S_y
 T_x T_y

Where:

• \(n\) and \(m\) are integers representing the number of rows and columns respectively.
• Each of the next \(n\) lines contains a string of length \(m\) representing a row of the grid.
• \(S_x, S_y\) denote the starting cell coordinates (0-indexed).
• \(T_x, T_y\) denote the target cell coordinates (0-indexed).

outputFormat

The output is a single integer printed to standard output (stdout): the length of the shortest path from the start to the target, or -1 if no such path exists.

## sample

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

8

</p>