Minimum Moves to Reach Target

You are given a grid with \(n\) rows and \(m\) columns. Each cell of the grid is either open ('.') or blocked ('#'). You are also given the starting position \((s_x, s_y)\) and the target position \((t_x, t_y)\), where the coordinates are 0-indexed. In one move, you can move one step in one of the four cardinal directions (up, down, left, or right).

Your task is to compute the minimum number of moves required for the robot to reach the target cell from the starting cell. If the target is unreachable, output \(-1\).

The problem can be formally described as follows:

• Let the grid be represented as a matrix \(G\) of size \(n \times m\), where \(G_{i,j} = '.'\) if the cell is open and \(G_{i,j} = '#'\) if the cell is blocked.
• Starting from \( (s_x, s_y) \) and moving in one of the four directions at each step, find the shortest path to \( (t_x, t_y) \).
• If either the start or target cell is blocked or if no path exists, the answer is \(-1\).

This problem is typically solved using a breadth-first search (BFS) algorithm.

inputFormat

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

 n m
 grid_row_1
 grid_row_2
 ...
 grid_row_n
 s_x s_y t_x t_y

Where:

• \(n\) and \(m\) are integers representing the number of rows and columns of the grid respectively.
• Each of the next \(n\) lines contains a string of length \(m\) composed of characters '.' and '#' representing the grid.
• The last line contains four integers: \(s_x\), \(s_y\), \(t_x\), \(t_y\) which denote the starting and target coordinates (0-indexed).

outputFormat

Output a single integer to standard output (stdout): the minimum number of moves required to reach the target cell. If the target is unreachable, output \(-1\).

## sample

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

8